2020/07/20 by Mahankali, Arvind V., Woodruff, David P.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2007.10307
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 O(k) columns and achieving an O(k1/2)-approximation for any k, improving upon the previous best O(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 A in 2poly(k/ε) + poly(nd) running time such that: ‖A - A‖p ≤ (1 + ε) ⋅ OPT + (ε)/(poly(k))‖A‖p where OPT = minAk rank k ‖A - Ak‖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 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.