Optimal ℓ_1 Column Subset Selection and a Fast PTAS for Low Rank Approximation
share
We study the problem of entrywise ℓ_1 low rank approximation. We give the first polynomial time column subset selection-based ℓ_1 low rank approximation algorithm sampling Õ(k) columns and achieving an Õ(k^1/2)-approximation for any k, improving upon the previous best Õ(k)-approximation and matching a prior lower bound for column subset selection-based ℓ_1-low rank approximation which holds for any poly(k) number of columns. We extend our results to obtain tight upper and lower bounds for column subset selection-based ℓ_p low rank approximation for any 1 < p < 2, closing a long line of work on this problem. We next give a (1 + ε)-approximation algorithm for entrywise ℓ_p low rank approximation, for 1 ≤ p < 2, that is not a column subset selection algorithm. First, we obtain an algorithm which, given a matrix A ∈ℝ^n × d, returns a rank-k matrix  in 2^poly(k/ε) + poly(nd) running time such that: A - Â_p ≤ (1 + ε) · OPT + ε/poly(k)A_p where OPT = min_A_k rank kA - A_k_p. Using this algorithm, in the same running time we give an algorithm which obtains error at most (1 + ε) · OPT and outputs a matrix of rank at most 3k — these algorithms significantly improve upon all previous (1 + ε)- and O(1)-approximation algorithms for the ℓ_p low rank approximation problem, which required at least n^poly(k/ε) or n^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^poly(k) + poly(nd) running time and the above additive error guarantee.
READ FULL TEXT