Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss

NeurIPS 2019

TL;DR

This paper tackles the challenge of 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 introduce a novel algorithm that achieves a near-linear time approximation for this problem under a mild assumption on the noise distribution, overcoming previous theoretical lower bounds.

What Problem Does This Paper Address?

The problem of low-rank matrix approximation is fundamental in many data science applications, akin to Principal Component Analysis (PCA). While minimizing the Frobenius norm (a standard measure of error) is well-studied and efficiently solvable, the $\ell_1$-norm loss presents a harder challenge. The $\ell_1$-norm is more robust to outliers and serves as a relaxation for the $\ell_0$-loss, which is relevant in areas like sparse recovery.

A key variant is column subset selection: instead of picking any low-rank matrix, we want to find a low-rank matrix that can be formed by a subset of the original matrix's columns. This is crucial for interpretability and efficiency. However, previous work showed that for the $\ell_1$-norm loss, achieving a good approximation (within $(1+\epsilon)$ of the optimal) requires an impractically large number of columns in the worst case. This paper aims to bridge this gap by showing that under a realistic assumption about the noise in the data, a good approximation is possible with a significantly smaller, near-linear number of columns and in near-linear time.

Methods

The paper introduces a novel algorithm that leverages a specific noise model: the input matrix $A$ is assumed to be a sum of a low-rank matrix $A^*$ and a noise matrix $\Delta$, where the entries of $\Delta$ are i.i.d. from a symmetric distribution with a bounded $p$-th moment for some $p > 1$. This assumption is crucial because it allows for "averaging" to reduce the noise's impact.

The core algorithmic idea involves:

  1. Sampling and Regression: A small set of columns is sampled. Then, for each of the remaining columns, an approximate $\ell_1$-regression is performed to see how well it can be represented by the sampled columns. This helps identify "good" columns that are well-approximated.
  2. Identifying "Heavy" Columns: The algorithm identifies and isolates "heavy" columns that contain very large entries. These columns are handled separately.
  3. Averaging and Covering: For the "non-heavy" columns, the algorithm uses multiple independent samples of column subsets. By averaging the results of fitting these columns using different subsets, the noise is effectively reduced, allowing for a $(1+\epsilon)$-approximation. This is a key insight that bypasses the worst-case lower bounds.
  4. Subroutine for General Matrices: The algorithm also utilizes a subroutine for $\ell_1$-norm low-rank approximation on general matrices, which provides an approximate solution with a larger rank or approximation factor.

Datasets

The paper evaluates its proposed algorithm (Algorithm 2, a heuristic version) on:

  • Synthetic Data: A 500x500 matrix generated with entries drawn uniformly from a specific distribution.
  • Real Datasets:
    • isolet (617x1559)
    • mfeat (651x2000)

Two types of noise distributions were tested:

  • A standard Lévy 1.1-stable distribution.
  • A distribution derived from the Cauchy distribution by taking the $1/\sqrt{2}$-th power of the absolute value.

Both noise distributions have a bounded 1.1-th moment but not a $p$-th moment for any $p > 1.1$, making them challenging for standard methods.

Key Insights and Ideas

  • Averaging Noise is Key: The paper demonstrates that even with heavy-tailed noise distributions (which can have infinite variance), if a $p$-th moment ($p>1$) exists, averaging multiple noisy estimates can significantly reduce the noise's impact. This is the core idea that allows for efficient approximation.
  • "Heavy" Columns are Manageable: The existence of a $p$-th moment ($p>1$) implies that only a small fraction of columns will contain extremely large entries. These "heavy" columns can be isolated and handled with a less precise approximation algorithm without compromising the overall result.
  • Bridging Theory and Practice: The theoretical results provide a strong guarantee under specific distributional assumptions. The paper also proposes a practical heuristic (Algorithm 2) inspired by these ideas, which shows strong empirical performance.
  • Overcoming Lower Bounds: The work provides the first algorithm that achieves a $(1+\epsilon)$-approximation for entrywise $\ell_1$-norm low-rank approximation in near-linear time, under mild distributional assumptions, effectively bypassing known worst-case lower bounds.

Key Results

  • Theoretical Guarantee: The paper presents an algorithm that, under the assumption of a symmetric noise distribution with a bounded $p$-th moment ($p>1$), can find a column subset $S$ of size $|S| \le \text{poly}(k/\epsilon) + O(k \log n)$ such that the $\ell_1$-norm error of the best rank-$k$ approximation using columns from $S$ is within $(1+\epsilon)$ of the optimal $\ell_1$-norm error. This is achieved in $O(n^2 + n \cdot \text{poly}(k/\epsilon))$ time with high probability.
  • Hardness Result: They also show that if the first moment of the noise distribution does not exist, then obtaining even a $(1+\epsilon)$-approximation is impossible, even with an arbitrary number of columns. This highlights the necessity of their distributional assumption.
  • Empirical Performance: Algorithm 2 (a median-based heuristic) 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 across various noise distributions and rank parameters. The approximation ratios were consistently lower for Algorithm 2.

Limitations and Future Work

  • Distributional Assumption: The theoretical results rely on the assumption that the noise distribution has a bounded $p$-th moment for some $p>1$. While this is milder than requiring Gaussian noise, it is still a specific assumption. The paper acknowledges that distributions like the standard Lévy 1.1-stable distribution (used in experiments) do not satisfy this for $p>1.1$.
  • Near-Linear Time: The theoretical algorithm runs in $O(n^2 + n \cdot \text{poly}(k/\epsilon))$ time. While this is near-linear in $n$ for fixed $k$ and $\epsilon$, the $n^2$ term might still be prohibitive for very large matrices. The empirical results use a heuristic that is likely faster.
  • Future Work: The paper's success with a median-based heuristic suggests that exploring other robust statistics for noise reduction could be fruitful. Further investigation into algorithms that can handle noise distributions with even weaker moment conditions would also be valuable.

Summary updated

BibTeX
@inproceedings{2019average,
  title = {{Average Case Column Subset Selection for Entrywise $\textbackslash\{\}ell\_1$-Norm Loss}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure