Tighter Low-rank Approximation via Sampling the Leveraged Element

By Srinadh Bhojanapalli, Prateek Jain, Sujay Sanghavi. 2014

37 citations recorded by the source corpus.

In this work, we propose a new randomized algorithm for computing a low-rank approximation to a given matrix. Taking an approach different 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κ2r5/e2) computations to generate a rank-r approximation to M in spectral norm. In contrast, the best existing method requires O(nnz(M)+nr2/e4) time to compute an approximation in Frobenius norm. Besides the tightness in spectral norm, we have a better dependence on the error e. 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 efficient 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 different 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).

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Optimization, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “Finally, two related works are [Bhojanapalli et al., 2015a,b].”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, methodology): “This approximation guarantee is comparable to the guarantee achieved in [BJS15] using diﬀerent techniques, but we avoid the condition number dependence in their method.”
Optimal principal component analysis in distributed and streaming models (2015, methodology): “A recent body of work [24, 6, 33, 26, 30, 9] (see Section 2 for a comparison) has focused on designing algorithms which minimize the communication needed for each machine to output an m × k matrix U for which , where A k ∈ R m × n is the best rank-k approximation to A .”