Optimal ℓ1 Column Subset Selection and a Fast PTAS for Low Rank Approximation

Arvind V. Mahankali, David P. Woodruff

This paper tackles the challenging problem of low-rank approximation, particularly focusing on the entrywise $\ell_1$ norm, which is more robust to outliers than the standard Frobenius norm. The authors present novel algorithms for both column subset selection and general low-rank approximation, achieving near-optimal approximation factors and significantly improving runtime complexities, especially for parameterized settings.

TL;DR

This paper introduces the first polynomial-time algorithms for $\ell_1$ column subset selection that achieve near-optimal approximation factors, significantly improving upon previous results. It also provides a fast $(1+\epsilon)$-approximation algorithm for general $\ell_1$ low-rank approximation, running in time polynomial in the matrix dimensions and $\epsilon$, which is a major breakthrough for parameterized complexity.

What Problem Does This Paper Address?

Low-rank approximation is a fundamental problem in data science, aiming to represent a large matrix $A$ as a product of two smaller matrices $U \cdot V$ (where $U \in \mathbb{R}^{n \times k}$ and $V \in \mathbb{R}^{k \times d}$), effectively compressing the data and enabling faster computations. While the Frobenius norm (sum of squared differences) is widely used, it's sensitive to outliers. The entrywise $\ell_1$ norm (sum of absolute differences) is more robust, but finding optimal $\ell_1$ low-rank approximations is computationally harder, even NP-hard.

A specific variant, column subset selection, aims to find a low-rank approximation where the columns of $U$ are a subset of the original columns of $A$. This is crucial for interpretability and feature selection. Prior work established hardness results showing that achieving a near-optimal approximation factor for $\ell_1$ column subset selection is challenging, with lower bounds suggesting a $k^{1/2-\gamma}$ approximation is the best possible for any polynomial-time algorithm. For general $\ell_1$ low-rank approximation, existing algorithms with $(1+\epsilon)$ approximation factors had prohibitively high running times, often dependent on the matrix dimensions $n$ and $d$ in a super-polynomial way for parameterized complexity.

This paper addresses two main questions:

  1. What is the best approximation factor achievable for $\ell_1$ column subset selection in polynomial time?
  2. Can we achieve a $(1+\epsilon)$ approximation for $\ell_1$ low-rank approximation in polynomial time, especially for parameterized settings where $k$ is small, without requiring strong bit complexity assumptions?

Methods

The paper introduces several novel algorithmic techniques:

  • Lewis Weight Sampling: For column subset selection, the authors leverage $\ell_p$ Lewis weights (a generalization of $\ell_1$ Lewis weights) to design sampling strategies. This allows them to select a subset of columns that can approximate the remaining columns with a controlled error.
  • Randomized Rounding and LP Relaxation: For general $\ell_1$ low-rank approximation, a key innovation is the use of randomized rounding on a linear programming (LP) relaxation. This technique is applied to a median-based sketching approach, allowing for a $(1+\epsilon)$ approximation with a bicriteria rank of $3k$. This is a significant departure from previous methods that relied on polynomial system solvers or had super-polynomial dependencies on $n$ and $d$.
  • Median-Based Sketches: The algorithms build upon existing work using median-based sketches with $p$-stable random variables. These sketches are crucial for estimating $\ell_p$ norms and preserving important properties of the matrix under linear transformations.
  • Deterministic Embeddings: To establish hardness results, the paper uses deterministic embeddings from $\ell_p$ to $\ell_1$ spaces, which are crucial for reducing problems to constrained versions.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and hardness results for general matrices, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Near-Optimal $\ell_1$ Column Subset Selection: The paper demonstrates that it's possible to achieve approximation factors for $\ell_1$ column subset selection that are nearly optimal, closing a long-standing gap between upper and lower bounds. This is achieved by carefully analyzing sampling strategies based on $\ell_p$ Lewis weights.
  • Fast $(1+\epsilon)$ $\ell_1$ Low-Rank Approximation: The introduction of randomized rounding on an LP relaxation for median-based sketches is a major algorithmic breakthrough. It allows for a $(1+\epsilon)$ approximation in time that is polynomial in $n, d, k,$ and $1/\epsilon$, which is crucial for parameterized complexity.
  • Bridging Theory and Practice: The algorithms presented are designed to be practical, avoiding super-polynomial dependencies on matrix dimensions and not requiring strong bit complexity assumptions, which were limitations of prior work.
  • Unified Framework for $\ell_p$ Norms: The paper provides a unified treatment for $\ell_p$ low-rank approximation for $p \in [1, 2)$, establishing tight bounds for column subset selection and efficient approximation algorithms.

Key Results

  • $\ell_1$ Column Subset Selection:
    • An algorithm that samples $O(k \log k \log d)$ columns and achieves an $O(\sqrt{k} \log^{3/2} k)$-approximation for $\ell_1$ low-rank approximation.
  • For $1 < p < 2$, an algorithm that chooses $O(k \log k (\log \log k)^2 \log d)$ columns and provides an $O(k^{1/p - 1/2} (\log k)^{2/p - 1/2} (\log \log k)^{2/p})$-approximation.
  • The paper also proves lower bounds for $1 < p < 2$, showing that any column subset selection algorithm with $k$ columns has an approximation factor of at least $k^{1/p - 1/2 - \gamma}$.
  • General $\ell_1$ Low-Rank Approximation:
    • A $(1+\epsilon)$-approximation algorithm with a bicriteria rank of $3k$ and running time $2^{\text{poly}(k/\epsilon)} + \text{poly}(nd)$. This is a significant improvement over previous algorithms that required $n^{\text{poly}(k/\epsilon)}$ time.
  • Hardness Results:
    • The paper establishes hardness results for $\ell_p$ low-rank approximation with additive error, showing that achieving an $O(1)$-approximation requires $2^{\Omega(k)}$ time, even with a $1/\text{poly}(k) \cdot \|A\|_p$ additive error term.
  • Hardness results are also shown for constrained $\ell_1$ low-rank approximation.

Limitations and Future Work

  • Approximation Factors: While the paper achieves near-optimal results for column subset selection, there might still be small gaps between the upper and lower bounds for $1 < p < 2$.
  • Bicriteria Rank: The general $(1+\epsilon)$-approximation algorithm for $\ell_1$ low-rank approximation has a bicriteria rank of $3k$. Reducing this rank further while maintaining the approximation factor and runtime is a potential direction for future work.
  • Empirical Evaluation: The paper is primarily theoretical. Future work could involve implementing these algorithms and evaluating their performance on real-world datasets, especially in comparison to existing methods.
  • Higher $p$ Values: The current work focuses on $p \in [1, 2)$. Extending these results to $p > 2$ or to the $\ell_\infty$ norm could be interesting.

Summary updated

Abstract

We study the problem of entrywise $\ell_1$ low rank approximation. We give the first polynomial time column subset selection-based $\ell_1$ low rank approximation algorithm sampling $\tilde{O}(k)$ columns and achieving an $\tilde{O}(k^{1/2})$-approximation for any $k$, improving upon the previous best $\tilde{O}(k)$-approximation and matching a prior lower bound for column subset selection-based $\ell_1$-low rank approximation which holds for any $\text{poly}(k)$ number of columns. We extend our results to obtain tight upper and lower bounds for column subset selection-based $\ell_p$ low rank approximation for any $1 < p < 2$, closing a long line of work on this problem. We next give a $(1 + \varepsilon)$-approximation algorithm for entrywise $\ell_p$ low rank approximation, for $1 \leq p < 2$, that is not a column subset selection algorithm. First, we obtain an algorithm which, given a matrix $A \in \mathbb{R}^{n \times d}$, returns a rank-$k$ matrix $\hat{A}$ in $2^{\text{poly}(k/\varepsilon)} + \text{poly}(nd)$ running time such that: $$\|A - \hat{A}\|_p \leq (1 + \varepsilon) \cdot OPT + \frac{\varepsilon}{\text{poly}(k)}\|A\|_p$$ where $OPT = \min_{A_k \text{ rank }k} \|A - A_k\|_p$. Using this algorithm, in the same running time we give an algorithm which obtains error at most $(1 + \varepsilon) \cdot OPT$ and outputs a matrix of rank at most $3k$ -- these algorithms significantly improve upon all previous $(1 + \varepsilon)$- and $O(1)$-approximation algorithms for the $\ell_p$ low rank approximation problem, which required at least $n^{\text{poly}(k/\varepsilon)}$ or $n^{\text{poly}(k)}$ running time, and either required strong bit complexity assumptions (our algorithms do not) or had bicriteria rank $3k$. Finally, we show hardness results which nearly match our $2^{\text{poly}(k)} + \text{poly}(nd)$ running time and the above additive error guarantee.
BibTeX
@inproceedings{mahankali2020optimal,
  author = {Arvind V. Mahankali and David P. Woodruff},
  title = {{Optimal ℓ1 Column Subset Selection and a Fast PTAS for Low Rank Approximation}},
  booktitle = {SODA},
  year = {2020},
  doi = {10.1137/1.9781611976465.34},
}
Figure