A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
From MaRDI portal
Abstract: We present randUBV, a randomized algorithm for matrix sketching based on the block Lanzcos bidiagonalization process. Given a matrix , it produces a low-rank approximation of the form , where and have orthonormal columns in exact arithmetic and is block bidiagonal. In finite precision, the columns of both and will be close to orthonormal. Our algorithm is closely related to the randQB algorithms of Yu, Gu, and Li (2018) in that the entries of are incrementally generated and the Frobenius norm approximation error may be efficiently estimated. Our algorithm is therefore suitable for the fixed-accuracy problem, and so is designed to terminate as soon as a user input error tolerance is reached. Numerical experiments suggest that the block Lanczos method is generally competitive with or superior to algorithms that use power iteration, even when has significant clusters of singular values.
Recommendations
- Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
- Randomized algorithms for the low-rank approximation of matrices
- Practical sketching algorithms for low-rank matrix approximation
- Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications
- A fast randomized algorithm for the approximation of matrices
Cites work
- A Block Lanczos Method for Computing the Singular Values and Corresponding Singular Vectors of a Matrix
- A Breakdown-Free Variation of the Nonsymmetric Lanczos Algorithms
- A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
- ABLE: An Adaptive Block Lanczos Method for Non-Hermitian Eigenvalue Problems
- An adaptive block Lanczos algorithm
- Band generalization of the Golub-Kahan bidiagonalization, generalized Jacobi matrices, and the core problem
- Block Krylov-Schur method for large symmetric eigenvalue problems
- Breakdown-free GMRES for Singular Systems
- Calculating the Singular Values and Pseudo-Inverse of a Matrix
- Convergence of the block Lanczos method for eigenvalue clusters
- Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications
- LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
- Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
- The block least squares method for solving nonsymmetric linear systems with multiple right-hand sides
- The block LSMR algorithm for solving linear systems with multiple right-hand sides
- The Lanczos Algorithm With Partial Reorthogonalization
- The Lanczos Algorithm with Selective Orthogonalization
- The University of Florida sparse matrix collection
Cited in
(6)- Improvement of the accuracy of the approximate solution of the Block BiCR method
- scientific article; zbMATH DE number 1735430 (Why is no real title available?)
- Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications
- Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
- Extended Lanczos bidiagonalization algorithm for low rank approximation and its applications
- Solution of large linear discrete ill-posed problems by randomized block Krylov methods
This page was built for publication: A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5863873)
