Fast and stable randomized low-rank matrix approximation

Abstract

Randomized SVD has become an extremely successful approach for efficiently computing a low-rank approximation of matrices. In particular the paper by Halko, Martinsson, and Tropp (SIREV 2011) contains extensive analysis, and has made it a very popular method. The typical complexity for a rank-$r$ approximation of $m\times n$ matrices is $O(mn\log n+(m+n)r^2)$ for dense matrices. The classical Nystr{ö}m method is much faster, but applicable only to positive semidefinite matrices. This work studies a generalization of Nystr{ö}m method applicable to general matrices, and shows that (i) it has near-optimal approximation quality comparable to competing methods, (ii) the computational cost is the near-optimal $O(mn\log n+r^3)$ for dense matrices, with small hidden constants, and (iii) crucially, it can be implemented in a numerically stable fashion despite the presence of an ill-conditioned pseudoinverse. Numerical experiments illustrate that generalized Nystr{ö}m can significantly outperform state-of-the-art methods, especially when $r\gg 1$, achieving up to a 10-fold speedup. The method is also well suited to updating and downdating the matrix.

References in corpus (4)

• The spectral norm error of the naive Nystrom extension
• A short proof of the Marchenko-Pastur theorem
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
• An improved analysis and unified perspective on deterministic and randomized low rank matrix approximations

Cited by in corpus (10)

• Learning elliptic partial differential equations with randomized linear algebra
• On convergence rates of adaptive ensemble Kalman inversion for linear ill-posed problems
• A Fast Randomized Algorithm for Computing an Approximate Null Space
• Fast & Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems
• Principled interpolation of Green's functions learned from data
• Randomised preconditioning for the forcing formulation of weak constraint 4D-Var
• High-Performance Partial Spectrum Computation for Symmetric eigenvalue problems and the SVD
• Fast randomized numerical rank estimation for numerically low-rank matrices
• Two-level Nyström--Schur preconditioner for sparse symmetric positive definite matrices
• A general error analysis for randomized low-rank approximation methods