Average Case Column Subset Selection for Entrywise 퓁1-Norm Loss

Zhao Song, David P. Woodruff, Peilin Zhong

Introduction

Principal Component Analysis (PCA) is the workhorse of dimensionality reduction, typically minimizing the Frobenius norm (the sum of squared errors). While computationally efficient via Singular Value Decomposition (SVD), the Frobenius norm is highly sensitive to outliers. The entrywise $\ell_1$-norm (the sum of absolute errors) is a much more robust alternative, but it comes with a steep computational price: it is NP-hard to solve exactly.

A common strategy for low-rank approximation is Column Subset Selection (CSS), where the goal is to find a small number of actual columns from the original matrix that can "span" the low-rank space. Previous research showed a depressing "worst-case" result: to get a good $\ell_1$ approximation for an $n \times n$ matrix, one might need to pick an impractically large number of columns ($n^{\Omega(1)}$).

This paper asks: Can we bypass these pessimistic lower bounds by assuming the data follows a reasonable distributional model (the "average case") rather than being maliciously constructed? The authors prove that under realistic conditions—where the data consists of a low-rank signal plus independent and identically distributed (i.i.d.) noise—one can achieve a near-optimal $(1+\epsilon)$-approximation in nearly linear time using only a small subset of columns.

Methods

The authors propose a bicriteria algorithm that achieves a $(1+\epsilon)$-approximation. Their approach relies on a fundamental insight: averaging reduces noise even in heavy-tailed distributions, provided at least a tiny bit more than the first moment exists.

The Theoretical Algorithm

The core theoretical contribution is an algorithm that systematically isolates and refines the column subset.

Algorithm 1 Pseudocode

The algorithm operates in several key phases:

  1. Sampling: Randomly sample a small set of columns $I$.
  2. Filtering: Use $\ell_1$-regression to identify which columns in the original matrix are not well-approximated by the sampled set $I$.
  3. Isolation: Take the "badly fit" columns and put them into a set $T$. These represent either the "heavy" noise columns or parts of the signal not yet captured.
  4. Refinement: Run a coarser, existing $\ell_1$ CSS algorithm on the small set $T$ to find a few more columns $Q$.
  5. Output: The final basis is the union of columns $I \cup Q$.

The Practical Heuristic

Alongside the theoretical algorithm, the authors introduce a "Median Heuristic." Instead of complex regression, they sample groups of columns and compute the entrywise median across those groups. Because the median is a robust estimator of the mean for symmetric distributions, this effectively "washes out" the noise to reveal the underlying low-rank signal.

Key Insights: The "Moment" Phase Transition

A major theoretical takeaway is the existence of a phase transition based on the noise distribution's moments. The existence of the $(1+\gamma)$-th moment (for any $\gamma > 0$) is the critical threshold. If it exists, the signal can be recovered efficiently. If it doesn't (such as in a standard Cauchy distribution where even the mean is undefined), the authors prove that no algorithm can efficiently find a good column subset, even if one chooses $n^{o(1)}$ columns.

By moving from "worst-case" to "average-case" analysis, the required number of columns drops from a polynomial of the matrix size ($n$) to a polynomial of the rank ($k$) and $\log n$. The paper mathematically formalizes why simple techniques like averaging or taking medians are so powerful for $\ell_1$ problems: they concentrate the noise faster than they dilute the signal.

Experimental Results

The researchers evaluated their approach on both synthetic data (random rank-$k$ matrices corrupted with heavy-tailed noise) and real-world datasets (ISOLET and MFEAT) injected with synthetic heavy-tailed noise.

  • Theoretical Efficiency: The algorithm achieves a $(1+\epsilon)$-approximation in $\tilde{O}(n^2)$ time, which is nearly linear in the number of entries in the matrix.
  • Column Efficiency: The number of columns selected is $\text{poly}(k/\epsilon) + O(k \log n)$, vastly improving upon the $n^{\Omega(1)}$ required in the worst case.
  • Empirical Superiority: In experiments, the Median Heuristic consistently outperformed standard SVD and previous state-of-the-art $\ell_1$ algorithms when the noise was heavy-tailed. It provided lower approximation ratios (closer to 1.0) across all tested ranks ($k=1$ to $10$).

Limitations and Future Work

The proposed algorithm is "bicriteria," meaning it might output a slightly higher rank than the target $k$ to achieve the $(1+\epsilon)$ error bound. Furthermore, the current proofs assume the noise is drawn from a symmetric distribution, whereas real-world noise can often be skewed. A natural next step for future research is investigating whether these average-case benefits extend to other robust loss functions, such as $L_p$ norms where $0 < p < 1$, or to more complex structural constraints like sparse PCA.

Summary updated

Abstract

We study the column subset selection problem with respect to the entrywise $\ell_1$-norm loss. It is known that in the worst case, to obtain a good rank-$k$ approximation to a matrix, one needs an arbitrarily large $n^{\Omega(1)}$ number of columns to obtain a $(1+\epsilon)$-approximation to an $n \times n$ matrix. Nevertheless, we show that under certain minimal and realistic distributional settings, it is possible to obtain a $(1+\epsilon)$-approximation with a nearly linear running time and poly$(k/\epsilon)+O(k\log n)$ columns. Namely, we show that if the input matrix $A$ has the form $A = B + E$, where $B$ is an arbitrary rank-$k$ matrix, and $E$ is a matrix with i.i.d. entries drawn from any distribution $\mu$ for which the $(1+\gamma)$-th moment exists, for an arbitrarily small constant $\gamma &gt; 0$, then it is possible to obtain a $(1+\epsilon)$-approximate column subset selection to the entrywise $\ell_1$-norm in nearly linear time. Conversely we show that if the first moment does not exist, then it is not possible to obtain a $(1+\epsilon)$-approximate subset selection algorithm even if one chooses any $n^{o(1)}$ columns. This is the first algorithm of any kind for achieving a $(1+\epsilon)$-approximation for entrywise $\ell_1$-norm loss low rank approximation.
BibTeX
@inproceedings{song2019average,
  author = {Zhao Song and David P. Woodruff and Peilin Zhong},
  title = {{Average Case Column Subset Selection for Entrywise 퓁1-Norm Loss}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=Ksl0eXJRG7Z},
}
Figure