In this work, we propose a new randomized algorithm for computing a low-rank approximation to a given matrix. Taking an approach di↵erent from existing literature, our method first involves a specific biased sampling, with an element being chosen based on the leverage scores of its row and column, and then involves weighted alternating minimization over the factored form of the intended low-rank matrix, to minimize error only on these samples. Our method can leverage input sparsity, yet produce approximations in spectral (as opposed to the weaker Frobenius) norm; this combines the best aspects of otherwise disparate current results, but with a dependence on the condition number = 1/r . In particular we require O(nnz(M)+ n2 r 5)computations to generate a rank-r approximation to M✏2in spectral norm. In contrast, the best existing method requires O (nnz (M)+ nr2) time to compute an approximation in Frobenius norm. Besides the tightness in spectral norm, we have a better dependence on the error. Our method is naturally and highly parallelizable.

Our new approach enables two extensions that are interesting on their own. The first is a new method to directly compute a low-rank approximation (in ecient factored form) to the product of two given matrices; it computes a small random set of entries of the product, and then executes weighted alternating minimization (as before) on these. The sampling strategy is diferent because now we cannot access leverage scores of the product matrix (but instead have to work with input matrices). The second extension is an improved algorithm with smaller communication complexity for the distributed PCA setting (where each server has small set of rows of the matrix, and want to compute low rank approximation with small amount of communication with other servers).