Fast and stable randomized low-rank matrix approximation

2020/09/23 by Yuji Nakatsukasa, Nakatsukasa, Yuji · 7 citations
Computer Science · Engineering · Mathematics · #65F55 #68W20 #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2009.11392

openalex publication_date 2020/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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× n matrices is O(mnlog n+(m+n)r²) 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(mnlog n+r³) 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≫ 1, achieving up to a 10-fold speedup. The method is also well suited to updating and downdating the matrix.

Citations

• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data

Cited by

• Numerical Stability of the Nyström Method
• A recursive butterfly factorization with optimality guarantees
• Splitting-based randomized dynamical low-rank approximations for stiff matrix differential equations
• On the randomized SVD in infinite dimensions
• A general error analysis for randomized low-rank approximation methods
• High-Performance Partial Spectrum Computation for Symmetric eigenvalue problems and the SVD
• Sharp error bounds for approximate eigenvalues and singular values from subspace methods

Related

• Fast monte-carlo algorithms for finding low-rank approximations
• Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
• Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications
• Subspace Iteration Randomization and Singular Value Problems
• A Rank Revealing Randomized Singular Value Decomposition (R3SVD)\n Algorithm for Low-rank Matrix Approximations