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

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 Õ(k1/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 of an n × d matrix, 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 2poly(k/∊) + poly(nd) running time that achieves the following guarantee: where . 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 npoly(k/∊) or npoly(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 2poly(k) +poly(nd) running time and the above additive error guarantee.