Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
By Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp. 2009
3,165 citations recorded by the source corpus.
Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed—either explicitly or implicitly—to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, robustness, and/or speed. These claims are supported by extensive numerical experiments and a detailed error analysis. The specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the $k$ dominant components of the singular value decomposition of an $m \times n$ matrix. (i) For a dense input matrix, randomized algorithms require $\bigO(mn \log(k))$ floating-point operations (flops) in contrast to $ \bigO(mnk)$ for classical algorithms. (ii) For a sparse input matrix, the flop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multiprocessor architectures. (iii) For a matrix that is too large to fit in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to $\bigO(k)$ passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data.
Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics, Optimization & Training
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
- Yoshua Bengio
- Michael I. Jordan
- Percy Liang
- Sergey Levine
- Quoc V. Le
- Mohit Bansal
- Ruslan Salakhutdinov
- Francis R. Bach
In Computational Mathematics
- Michael W. Mahoney
- David P. Woodruff
- Alex Gittens
- Joel A. Tropp
- Ameet Talwalkar
- Kenneth L. Clarkson
- Per-Gunnar Martinsson
- Francis R. Bach
In Computational Mechanics
- Francis R. Bach
- Steven L. Brunton
- Michael W. Mahoney
- Martin J. Wainwright
- J. Nathan Kutz
- Prateek Jain
- Peter Richtárik
- Joel A. Tropp
In Optimization & Training
- Simon Lacoste-Julien
- Peter Richtárik
- Francis R. Bach
- Nicolas Loizou
- Jakub Konecný
- Michael I. Jordan
- Aryan Mokhtari
- Martin Jaggi
Citations in the corpus
- Beyond CCA: Moment Matching for Multi-View Models (2016, positive): “When M 1 and M 2 are too large, one can use a randomized SVD algorithm (see, e.g., Halko et al., 2011) to avoid the construction of the large matrix S 12 and to decrease the computational time.”
- A literature survey of low‐rank tensor approximation techniques (2013, neutral): “Randomized algorithms represent an alternative way to quickly extract a low-rank approximation from partial information on the entries of the matrix, see [120] and the references therein.”
- A Simple Baseline for Bayesian Uncertainty in Deep Learning (2019, methodology): “In order to find these eigenvectors we use randomized SVD [21].”
- Fast Interpolation-based t-SNE for Improved Visualization of Single-Cell RNA-Seq Data (2017, methodology): “ which are easily parallelized, 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”
- User-Friendly Tail Bounds for Sums of Random Matrices (2010, methodology): “n by sparsification [AM07] and by sampling submatrices [RV07]; analysis of sparse approximation [Tro08] and compressive sampling [CR07] algorithms; randomized schemes for low-rank matrix factorization [HMT11]; and analysis of algorithms for completion of low-rank matrices [Gro11, Rec09]. And this lis”
- Iterative reweighted algorithms for matrix rank minimization (2012, methodology): “Randomized algorithms (e.g., Halko et al., 2011) can be used to compute the top r singular vectors and singular values of a matrix X efficiently, with small approximation errors, if σ r+1 (X) is small.”
- QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks (2024, methodology): “QuIP # uses the Randomized Hadamard Transform as an efficient and principled form of outlier suppression, and introduces the E 8 lattice-based E8P codebook to better quantize RHT transformed weights.”
- An Introduction to Matrix Concentration Inequalities (2015, positive): “The survey [80] explains how to implement this method in practice, while the two monographs [120, 193] cover more theoretical aspects.”
- Efficient matrix completion for seismic data reconstruction (2015, methodology): “, 2007; Halko et al., 2011; Mahoney, 2011) to interpolate seismic temporal frequency slices. While this technique may be effective for interpolating data with a limited number of distinct dips, first, the approach requires embedding the data into an even larger space where each dimension of size n i”
- Beating randomized response on incoherent matrices (2011, positive): “Our algorithms are most closely related to the very recent work of Halko, Martinsson, and Tropp [13], who give fast algorithms for computing low rank approximations based on two steps: range finding, and projection.”
- The spectral norm error of the naive Nystrom extension (2011, methodology): “To establish Theorem 1, we use the following bound on the error incurred by projecting a matrix onto a random subspace of its range ([HMT11, Theorem 9.1]).”
- RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images (2010, methodology): “These strategies include low-level tricks such as rank prediction [39], the use of the Lanczos algorithm for computing only a few singular vectors [40] with warm starts, as well as algorithmic modifications such as the use of randomized approximations to the SVD [41], [42].”
- Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “) random variables. 2. Let Z be an n ×k matrix with orthonormal columns whose column space is equal to that of Y. 3. Output ZZTA. In order to analyze SubspacePowerMethod, we need a key lemma shown in [59] concerning powering of a matrix. Lemma 59 Let P be a projection matrix, i.e., P = ZZT for a mat”
- Invertible generative models for inverse problems: mitigating representation error and dataset bias (2019, positive): “Proof of Theorem 1.”