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 the best entrywise $\ell_1$-norm low rank approximation of 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 $\text{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 > 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.
Introduction
Low-rank matrix approximation is a cornerstone of data science, most commonly seen in Principal Component Analysis (PCA). While standard PCA minimizes the Frobenius norm (the sum of squared errors), this approach is notoriously sensitive to outliers. The entrywise $\ell_1$-norm (the sum of absolute errors) is a much more robust alternative, but it is NP-hard to solve exactly.
A popular way to approximate a matrix is Column Subset Selection (CSS), where we find a small subset of the original columns that can span a space close to the best rank-$k$ approximation. Previous research showed a discouraging "worst-case" result: to get a high-precision $(1+\epsilon)$ approximation for $\ell_1$, one might need an impractically large number of columns ($n^{\Omega(1)}$). This paper provides the first efficient algorithm for $(1+\epsilon)$-approximate CSS under the entrywise $\ell_1$-norm by assuming a realistic "average case" noise model.
The Average Case Model
The authors analyze the "average case" where an input matrix $A$ is composed of a "ground truth" rank-$k$ matrix $B$ plus a noise matrix $E$ ($A = B + E$).
The entries of the noise matrix $E$ are i.i.d. and symmetric. Crucially, they assume the $(1+\gamma)$-th moment exists for some constant $\gamma > 0$. This mild assumption allows for "heavy-tailed" noiseโnoise with frequent large outliersโas long as it isn't as extreme as the Cauchy distribution (where the first moment does not exist).
The L1NoisyLowRankApprox Algorithm
The proposed algorithm, L1NoisyLowRankApprox, operates in nearly linear time $O(n^2 + n \cdot \text{poly}(k/\epsilon))$. The procedure leverages the property that if the $(1+\gamma)$ moment exists, averaging multiple noisy columns reduces noise faster than the signal, allowing a small sample to "cover" the majority of the matrix.
The algorithm follows these primary steps:
- Random Sampling: Sample a small subset of columns $I$ uniformly at random.
- $\ell_1$-Regression: Solve an approximate $\ell_1$-regression problem to estimate how well the sampled columns $I$ reconstruct every other column $A_i$.
- Identify "Hard" Columns: Identify the set $T$ of columns that are poorly reconstructed (the top $l$ largest errors). These columns likely contain significant noise or unique structural information not captured by the initial sample.
- Bicriteria Refinement: Run a coarser $\ell_1$ subset selection algorithm on the "hard" columns $A_T$ to find a small set $Q$.
- Final Output: Return the union of the sampled columns and the refined subset ($I \cup Q$), along with the solution $\hat{X}$ to the regression problem $\min \|A_{(I \cup Q)}X - A\|_1$.
Key Insights and Results
The core theoretical insight is the "Cauchy Boundary." The authors prove that if the first moment does not exist (e.g., standard Cauchy noise), it is impossible to obtain a $(1+\epsilon)$ approximation with a small number of columns. This identifies the exact mathematical threshold where efficient $\ell_1$ subset selection becomes feasible.
Empirical Performance
The algorithm was evaluated on both synthetic and real-world datasets:
- Synthetic Data: $500 \times 500$ matrices with 1.1-stable Lรฉvy and "Cauchy-root" noise.
- Real-World Data: ISOLET (speech recognition) and MFEAT (handwritten digit features).
In experiments, a practical variant called the "Median Heuristic" consistently outperformed standard SVD and other state-of-the-art $\ell_1$ algorithms across various noise levels. The algorithm's nearly linear runtime makes it highly scalable compared to previous methods.
Conclusion and Limitations
This work establishes the first $(1+\epsilon)$-approximation for entrywise $\ell_1$-norm low-rank approximation. While powerful, the theoretical guarantees depend on the noise being i.i.d. and symmetric. If noise is adversarial or highly structured, the averaging property may fail. Future work may explore median-based techniques to further improve practical performance and investigate whether the bicriteria set size can be reduced to exactly $k$ columns.
Summary updated