A block bidiagonalization method for fixed-accuracy low-rank matrix approximation

DOI10.1137/21M1397866zbMATH Open1492.65111arXiv2101.01247OpenAlexW4225266577MaRDI QIDQ5863873FDOQ5863873

Authors: Eric Hallman 

Publication date: 3 June 2022

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2101.01247

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

zbMATH Keywords

randomized algorithmlow-rank matrix approximationblock Lanczosfixed-accuracy problem

Mathematics Subject Classification ID

Randomized algorithms (68W20) Numerical computation of matrix norms, conditioning, scaling (65F35) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• The University of Florida sparse matrix collection
• LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
• ABLE: An Adaptive Block Lanczos Method for Non-Hermitian Eigenvalue Problems
• Title not available (Why is that?)
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Calculating the Singular Values and Pseudo-Inverse of a Matrix
• Breakdown-free GMRES for Singular Systems
• The block least squares method for solving nonsymmetric linear systems with multiple right-hand sides
• The Lanczos Algorithm With Partial Reorthogonalization
• A Breakdown-Free Variation of the Nonsymmetric Lanczos Algorithms
• Block Krylov-Schur method for large symmetric eigenvalue problems
• An adaptive block Lanczos algorithm
• Convergence of the block Lanczos method for eigenvalue clusters
• Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications
• A Block Lanczos Method for Computing the Singular Values and Corresponding Singular Vectors of a Matrix
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• The Lanczos Algorithm with Selective Orthogonalization
• The block LSMR algorithm for solving linear systems with multiple right-hand sides
• Band generalization of the Golub-Kahan bidiagonalization, generalized Jacobi matrices, and the core problem
• A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
• Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces

Cited In (5)

• Title not available (Why is that?)
• Extended Lanczos bidiagonalization algorithm for low rank approximation and its applications
• Improvement of the accuracy of the approximate solution of the Block BiCR method
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications

Uses Software

• Matlab
• SparseMatrix
• ABLE
• LSMR

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)