Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds

By Rafi Witten, E.J. Candes. 2013

78 citations recorded by the source corpus.

The development of randomized algorithms for numerical linear algebra, e.g. for computing approximate QR and SVD factorizations, has recently become an intense area of research. This paper studies one of the most frequently discussed algorithms in the literature for dimensionality reduction—specifically for approximating an input matrix with a low-rank element. We introduce a novel and rather intuitive analysis of the algorithm in [6], which allows us to derive sharp estimates and give new insights about its performance. This analysis yields theoretical guarantees about the approximation error and at the same time, ultimate limits of performance (lower bounds) showing that our upper bounds are tight. Numerical experiments complement our study and show the tightness of our predictions compared with empirical observations.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Fast Interpolation-based t-SNE for Improved Visualization of Single-Cell RNA-Seq Data (2017, background): “llelized, and for which highly optimized implementations exist. Randomized algorithms have been rigorously proven to be remarkably accurate with extremely high probability (e.g. Halko et al. (2011b); Witten and Candes (2015)), because for a rank-kmatrix, as few as l= k+2 random vectors are sucient f”
Randomized Matrix Decompositions using R (2016, background): “Further, Witten and Candes (2015) provide sharp error bounds and interesting theoretical insights.”
Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (2015, background): “A series of work [1, 2, 13, 14, 15] shows that the decades old Simultaneous Power Iteration (also called subspace iteration or orthogonal iteration) implemented with random start vectors, achieves (2) after Õ(1/ ) iterations.”
Distributed optimization for multi-task learning via nuclear-norm approximation (2015, methodology): “…try to overcome the nonsmooth nature of the nuclear norm, use techniques such as approximate singular value decompositions (Woolfe et al., 2008; Witten and Candès, 2015); coordinate descent and subspace selection (Dud́ık et al., 2012; Hsieh and Olsen, 2014); and successive over-relaxation…”
Robust Principal Component Analysis on Graphs (2015, methodology): “The large computation time of our model is dominated by the expensive SVD step in every iteration.”
Efficient Algorithms for t-distributed Stochastic Neighborhood Embedding (2017, background): “Randomized algorithms have been rigorously proven to be remarkably accurate with extremely high probability (e.g. Halko et al. (2011b); Witten and Candes (2015)), because for a rank-k matrix, as few as l = k+ 2 random vectors are sufficient for the probability of missing a significant part of the…”