On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation
Authors:
- Raphael A. MeyerRMRaphael A. Meyer
- Cameron MuscoCMCameron Musco
- Christopher MuscoCMChristopher Musco
Preprint
Abstract
Krylov subspace methods are a ubiquitous tool for computing near-optimal rank $k$ approximations of large matrices. While "large block" Krylov methods with block size at least $k$ give the best known theoretical guarantees, block size one (a single vector) or a small constant is often preferred in practice. Despite their popularity, we lack theoretical bounds on the performance of such "small block" Krylov methods for low-rank approximation. We address this gap between theory and practice by proving that small block Krylov methods essentially match all known low-rank approximation guarantees for large block methods. Via a black-box reduction we show, for example, that the standard single vector Krylov method run for $t$ iterations obtains the same spectral norm and Frobenius norm error bounds as a Krylov method with block size $\ell \geq k$ run for $O(t/\ell)$ iterations, up to a logarithmic dependence on the smallest gap between sequential singular values. That is, for a given number of matrix-vector products, single vector methods are essentially as effective as any choice of large block size. By combining our result with tail-bounds on eigenvalue gaps in random matrices, we prove that the dependence on the smallest singular value gap can be eliminated if the input matrix is perturbed by a small random matrix. Further, we show that single vector methods match the more complex algorithm of [Bakshi et al. `22], which combines the results of multiple block sizes to achieve an improved algorithm for Schatten $p$-norm low-rank approximation.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Krylov Methods are (nearly) Optimal for Low-Rank Approximation2023
- Subspace Iteration Randomization and Singular Value ProblemsSIAM Journal on Scientific Computing, 2015
- The Lanczos and conjugate gradient algorithms in finite precision arithmeticActa Numerica, 2006
- Random-matrix theory of quantum transportReviews of Modern Physics, 1997
- Local fluctuation of the spectrum of a multidimensional Anderson tight binding modelCommunications in Mathematical Physics, 1996
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random StartSIAM Journal on Matrix Analysis and Applications, 1992
- Bounds on the density of states in disordered systemsZeitschrift für Physik B Condensed Matter, 1981
- On the Rates of Convergence of the Lanczos and the Block-Lanczos MethodsSIAM Journal on Numerical Analysis, 1980
- The Block Lanczos Method for Computing Eigenvalues1977
- Computational Variants of the Lanczos Method for the EigenproblemIMA Journal of Applied Mathematics, 1972