Randomized algorithms for the low-rank approximation of matrices

Edo Liberty, Franco Woolfe, Per‐Gunnar Martinsson, Vladimir Rokhlin, Mark Tygert

Type: Article

Publication Date: 2007-12-05

Citations: 558

DOI: https://doi.org/10.1073/pnas.0709640104

Abstract

We describe two recently proposed randomized algorithms for the construction of low-rank approximations to matrices, and demonstrate their application (inter alia) to the evaluation of the singular value decompositions of numerically low-rank matrices. Being probabilistic, the schemes described here have a finite probability of failure; in most cases, this probability is rather negligible (10(-17) is a typical value). In many situations, the new procedures are considerably more efficient and reliable than the classical (deterministic) ones; they also parallelize naturally. We present several numerical examples to illustrate the performance of the schemes.

Locations

Proceedings of the National Academy of Sciences - View
PubMed Central - View
ePubWU Institutional Repository (Wirtschaftsuniversität Wien) - View - PDF
Europe PMC (PubMed Central) - View - PDF
PubMed - View

Similar Works

Action	Title	Year	Authors
+	Fast randomized numerical rank estimation for numerically low-rank matrices	2021	Maike Meier Yuji Nakatsukasa
+	Randomized algorithms for low-rank matrix factorizations: sharp performance bounds	2013	Rafi Witten Emmanuel J. Candès
+	Randomized algorithms for low-rank matrix factorizations: sharp performance bounds	2013	Rafi Witten Emmanuel J. Candès
+	Fast randomized numerical rank estimation for numerically low-rank matrices	2024	Maike Meier Yuji Nakatsukasa
+	Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions	2009	Nathan Halko Per‐Gunnar Martinsson Joel A. Tropp
+	Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions	2009	Nathan Halko Per‐Gunnar Martinsson Joel A. Tropp
+ PDF Chat	Subspace Iteration Randomization and Singular Value Problems	2015	Ming Gu
+	Randomized low-rank approximation of parameter-dependent matrices	2023	Daniel Kreßner Hei Yin Lam
+	Subspace Iteration Randomization and Singular Value Problems	2014	Ming Gu
+	Fast and stable randomized low-rank matrix approximation	2020	Yuji Nakatsukasa
+	Fast Low-Rank Approximation for Covariance Matrices	2007	Mohamed-Ali Belabbas Patrick J. Wolfe
+ PDF Chat	Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions	2011	Nathan Halko Per‐Gunnar Martinsson Joel A. Tropp
+	Fast Monte Carlo Algorithms for Computing a Low-Rank Approximation to a Matrix	2014	Vlad S Burca
+	Deterministic algorithms for the low rank approximation of matrices	2017	Xavier Vasseur
+	Randomized low‐rank approximation of parameter‐dependent matrices	2024	Daniel Kreßner Hei Yin Lam
+	Efficient random methods for low-rank matrix estimation	2025	Yu Mei Xiangchu Feng Qi He
+ PDF Chat	Randomized Rank-Revealing Qlp for Low-Rank Matrix Decomposition	2022	Maboud F. Kaloorazi Kai Liu Jie Chen Rodrigo C. de Lamare Susanto Rahardja
+	Randomized Rank-Revealing QLP for Low-Rank Matrix Decomposition	2022	Maboud F. Kaloorazi Kai Liu Jie Chen Rodrigo C. de Lamare Susanto Rahardja
+	Low-rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions	2015	Victor Y. Pan Liang Zhao
+ PDF Chat	Randomized Rank-Revealing QLP for Low-Rank Matrix Decomposition	2023	Maboud F. Kaloorazi K.-H. Liu Jie Chen Rodrigo C. de Lamare Susanto Rahardja

Works That Cite This (313)

Action	Title	Year	Authors
+	Randomized interpolative decomposition of separated representations	2014	David Biagioni Daniel Beylkin Gregory Beylkin
+ PDF Chat	FaIMS: A fast algorithm for the inverse medium problem with multiple frequencies and multiple sources for the scalar Helmholtz equation	2012	Stéphanie Chaillat George Biros
+ PDF Chat	NFFT Meets Krylov Methods: Fast Matrix-Vector Products for the Graph Laplacian of Fully Connected Networks	2018	Dominik Alfke Daniel Potts Martin Stoll Toni Volkmer
+	How to Reduce Dimension With PCA and Random Projections?	2021	Fan Yang Sifan Liu Edgar Dobriban David P. Woodruff
+ PDF Chat	Fast randomized matrix and tensor interpolative decomposition using CountSketch	2020	Osman Asif Malik Stephen Becker
+	Fast Algorithms for Approximating the Singular Value Decomposition	2011	Aditya Krishna Menon Charles Elkan
+ PDF Chat	Butterfly Factorization	2015	Yingzhou Li Haizhao Yang Eileen Martin Kenneth L. Ho Lexing Ying
+	Reducing the amount of out‐of‐core data access for GPU‐accelerated randomized SVD	2020	Yuechao Lu Ichitaro Yamazaki Fumihiko Ino Yasuyuki Matsushita Stanimire Tomov Jack Dongarra
+	Randomized CP tensor decomposition	2020	N. Benjamin Erichson Krithika Manohar Steven L. Brunton J. Nathan Kutz
+	Hybrid reduced order modeling applied to nonlinear models	2012	Youngsuk Bang Hany S. Abdel‐Khalik Jason Hite

Works Cited by This (6)

Action	Title	Year	Authors
+	Estimating Extremal Eigenvalues and Condition Numbers of Matrices	1983	John D. Dixon
+ PDF Chat	Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start	1992	J. Kuczyński H. Woźniakowski
+ PDF Chat	Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization	1996	Ming Gu Stanley C. Eisenstat
+	A Randomized Algorithm for the Approximation of Matrices	2006	Per‐Gunnar Martinsson Vladimir Rockhlin Mark Tygert
+	A fast randomized algorithm for the approximation of matrices	2007	Franco Woolfe Edo Liberty Vladimir Rokhlin Mark Tygert
+ PDF Chat	On interpolation and integration in finite-dimensional spaces of bounded functions	2006	Per‐Gunnar Martinsson Vladimir Rokhlin Mark Tygert