TL;DR
This paper introduces a novel algorithm for finding a low-rank approximation of a matrix using a subset of its columns, specifically when the error is measured by the $\ell_1$-norm. They demonstrate that under realistic noise assumptions (specifically, that the noise has a finite $p$-th moment for some $p>1$), it's possible to achieve a near-perfect approximation $(1+\epsilon)$ with a near-linear runtime and a significantly smaller number of columns than previously thought possible.
What Problem Does This Paper Address?
In many data analysis tasks, we encounter large matrices that can be approximated by a lower-rank matrix. A common goal is to find a rank-$k$ matrix $B$ that is "close" to the original matrix $A$. The "closeness" is often measured by a norm of the difference $A-B$. While the Frobenius norm (essentially the Euclidean distance) is widely used and has efficient solutions, the $\ell_1$-norm (sum of absolute differences) is more robust to outliers and is a relaxation of the $\ell_0$-norm (counting non-zero entries), which is relevant in areas like sparse recovery.
The challenge is that finding the optimal $\ell_1$-norm low-rank approximation is NP-hard. A related problem is "column subset selection," where we aim to find a small subset of columns from the original matrix $A$ that can be used to reconstruct a good low-rank approximation. Previous work showed that for $\ell_1$-norm approximation, achieving a $(1+\epsilon)$ accuracy in the worst case requires an impractically large number of columns. This paper tackles the question: can we do better if we relax the "worst-case" assumption and instead consider "average-case" scenarios with certain realistic noise properties?
Methods
The core of the paper's contribution lies in developing an algorithm that bypasses the worst-case lower bounds by making a mild assumption on the noise distribution. Specifically, they assume the input matrix $A$ can be written as $A = A^* + \Delta$, where $A^*$ is the true low-rank matrix and $\Delta$ is a noise matrix. The crucial assumption is that the entries of $\Delta$ are independent and identically distributed (i.i.d.) from a symmetric distribution that has a finite $p$-th moment for some $p > 1$. This is a weaker condition than requiring Gaussian noise, allowing for heavier tails.
The algorithm leverages several key ideas:
- Averaging for Noise Reduction: A central insight is that averaging multiple noisy estimates can reduce the impact of noise. This is demonstrated with a toy example and formalized in Lemma 2.2, showing that averaging linear combinations of noisy vectors reduces their $\ell_1$-norm error.
- "Good" Columns and "Heavy" Columns: They categorize columns based on the magnitude of their entries. "Good" columns have entries below a certain threshold, while "heavy" columns have at least one large entry. The algorithm handles these differently.
- Column Subset Selection with $\ell_1$-Regression: The algorithm uses an approximate $\ell_1$-regression solver as a subroutine. This solver can efficiently find coefficients to fit a target vector using a given set of columns, minimizing the $\ell_1$-norm error.
- Covering Columns: The algorithm aims to "cover" most columns by showing that they can be well-approximated by a small subset of sampled columns. The "covering" condition is defined in terms of the $\ell_1$-regression error.
- Bicriteria Approximation: The algorithm provides a $(1+\epsilon)$-approximation to the optimal $\ell_1$-norm low-rank approximation, but it uses a subset of columns whose size is bounded by poly$(k/\epsilon) + O(k \log n)$, which is significantly smaller than the worst-case requirement.
Datasets
The paper evaluates their proposed heuristic algorithm (Algorithm 2) on:
- Synthetic Data: A 500x500 matrix with entries drawn uniformly from a 1.1-stable distribution and a scaled Cauchy distribution.
- Real Datasets: The
isoletdataset (617x1559) and themfeatdataset (651x2000).
For these experiments, they generated a ground truth rank-$k$ matrix $A^*$ using Singular Value Decomposition (SVD) on a high-rank matrix, and then added noise to create the input matrix $A$.
Key Insights and Ideas
- The Power of Bounded Moments: The paper shows that the existence of a finite $p$-th moment for the noise distribution (even for $p$ just slightly larger than 1) is sufficient to overcome worst-case lower bounds for $\ell_1$-norm low-rank approximation. This is a significant relaxation of typical noise assumptions.
- Averaging as a Noise Mitigation Strategy: The core algorithmic idea of using multiple sampled subsets to average approximations is crucial. This allows for a more robust fit and reduces the error compared to single-sample approaches.
- Bridging Theory and Practice: While the main theoretical result is for a specific noise model, the paper also proposes a practical "Median Heuristic" algorithm (Algorithm 2) that performs well empirically, suggesting the underlying principles are broadly applicable.
- Necessity of the Moment Assumption: The paper also provides a hardness result, showing that if the first moment of the noise distribution does not exist (e.g., for a standard Cauchy distribution), then even an $n^{o(1)}$ column subset is insufficient for a $(1+\epsilon)$ approximation. This highlights the critical role of the moment assumption.
Key Results
- Theoretical Result: An algorithm is presented that achieves a $(1+\epsilon)$-approximate $\ell_1$-norm low-rank approximation using a subset of columns of size poly$(k/\epsilon) + O(k \log n)$ in nearly linear time, provided the noise has a finite $p$-th moment ($p>1$). This is the first algorithm to achieve such a guarantee for $\ell_1$-norm loss.
- Hardness Result: If the first moment of the noise distribution does not exist, it's impossible to achieve a $(1+\epsilon)$-approximation with $n^{o(1)}$ columns.
- Empirical Results: A proposed heuristic algorithm (Algorithm 2) based on median filtering and column sampling outperformed existing methods (SVD, $\ell_1$-norm low-rank approximation from [24], and uniform k-column subset sampling from [25]) on synthetic and real datasets in terms of approximation ratio.
Limitations and Future Work
- Noise Model Specificity: The theoretical results are contingent on the noise distribution having a finite $p$-th moment for some $p>1$. While this is a weaker assumption than Gaussian noise, it still excludes distributions like the standard Cauchy distribution (which has a finite first moment but infinite variance).
- Heuristic Performance: While Algorithm 2 performed well empirically, it is a heuristic and lacks the theoretical guarantees of the main algorithm.
- Future Work: The authors suggest exploring the performance of their algorithms on other types of noise distributions and investigating further improvements to the running time. The paper also opens avenues for exploring similar techniques for other norms or matrix approximation problems.
Summary updated