Optimal ${\ell }_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation

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+\epsilon )$-approximation algorithm for entrywise ${\ell }_p$ low rank approximation, for $1\le 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/\epsilon )}+\text{poly}(nd)$ running time such that: $$\Vert A-\hat{A}{\Vert }_p\le (1+\epsilon )\cdot OPT+\frac{\epsilon }{\text{poly}(k)}\Vert A{\Vert }_p$$ where $OPT={\min }_{A_k\text{ rank }k}\Vert A-A_k{\Vert }_p$. Using this algorithm, in the same running time we give an algorithm which obtains error at most $(1+\epsilon )\cdot OPT$ and outputs a matrix of rank at most $3k$ -- these algorithms significantly improve upon all previous $(1+\epsilon )$- and $O(1)$-approximation algorithms for the ${\ell }_p$ low rank approximation problem, which required at least $n^{\text{poly}(k/\epsilon )}$ 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.

arXiv commentTo appear in SODA 2021. Changes: (1) Fixed errors in hardness proof for constrained ${\ell }_1$ low rank approximation. (2) Simplified analysis of column subset selection algorithm. (3) Improved runtime of $\text{poly}(k)$-approximation algorithm with output rank $k$ from $2^{O(k\log k)}+\text{poly}(nd)$ to $\text{poly}(nd)$. Results are unchanged aside from (3)

References in corpus (7)

• Hypercontractivity, Sum-of-Squares Proofs, and their Applications
• Optimal Algorithms for $L_1$-subspace Signal Processing
• Efficient L1-Norm Principal-Component Analysis via Bit Flipping
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Near-Optimal Column-Based Matrix Reconstruction
• Iteratively Reweighted Least Squares Algorithms for L1-Norm Principal Component Analysis
• Simple and practical algorithms for ${\ell }_p$-norm low-rank approximation