Improved Algorithms for Low Rank Approximation from Sparsity

We overcome two major bottlenecks in the study of low rank approximation by assuming the low rank factors themselves are sparse. Specifically, (1) for low rank approximation with spectral norm error, we show how to improve the best known nnz(A)k/ √ ε running time to nnz(A)/ √ ε running time plus low order terms depending on the sparsity of the low rank factors, and

(2) for streaming algorithms for Frobenius norm error, we show how to bypass the known Ω(nk/ε) memory lower bound and obtain an sk(log n)/ poly(ε) memory bound, where s is the number of non-zeros of each low rank factor. Although this algorithm runs in exponential time, as it must under standard complexity-theoretic assumptions, we also present polynomial time algorithms using poly(s, k, log n, ε -1 ) memory that output rank k approximations supported on an O(sk/ε)×O(sk/ε) submatrix.

Both the prior nnz(A)k/ √ ε running time and the nk/ε memory for these problems were long-standing barriers; our results give a natural way of overcoming them assuming sparsity of the low rank factors.