Approximation Algorithms for $\ell_0$-Low Rank Approximation
Authors: Karl Bringmann, Pavel Kolev, David Woodruff
NeurIPS 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide approximation algorithms which significantly improve the running time and approximation factor of previous work. To the best of our knowledge, this is the first algorithm with provable guarantees for the ℓ0-Low Rank Approximation Problem for k > 1, even for bicriteria algorithms. |
| Researcher Affiliation | Academia | 1 Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany 2 Department of Computer Science, Carnegie Mellon University |
| Pseudocode | Yes | Algorithm 1 Selecting O(k log(n/k)) columns of A. ... Algorithm 2 Input: A Rm n and ϵ (0, 0.1). ... Algorithm 3 Input: A Rm n, u Rm and ϵ (0, 1). |
| Open Source Code | No | The paper does not provide any specific links or explicit statements about the release of source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not describe experiments on specific public datasets nor does it provide access information for any datasets. |
| Dataset Splits | No | The paper focuses on theoretical algorithms and their analysis, and does not provide specific details regarding training, validation, or test dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical algorithms and does not specify any hardware details used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific ancillary software components with version numbers needed to replicate experiments. |
| Experiment Setup | No | The paper is theoretical and does not provide specific experimental setup details such as hyperparameter values or training configurations. |