Subspace Iteration Randomization and Singular Value Problems
From MaRDI portal
Abstract: A classical problem in matrix computations is the efficient and reliable approximation of a given matrix by a matrix of lower rank. The truncated singular value decomposition (SVD) is known to provide the best such approximation for any given fixed rank. However, the SVD is also known to be very costly to compute. Among the different approaches in the literature for computing low-rank approximations, randomized algorithms have attracted researchers' recent attention due to their surprising reliability and computational efficiency in different application areas. Typically, such algorithms are shown to compute with very high probability low-rank approximations that are within a constant factor from optimal, and are known to perform even better in many practical situations. In this paper, we present a novel error analysis that considers randomized algorithms within the subspace iteration framework and show with very high probability that highly accurate low-rank approximations as well as singular values can indeed be computed quickly for matrices with rapidly decaying singular values. Such matrices appear frequently in diverse application areas such as data analysis, fast structured matrix computations and fast direct methods for large sparse linear systems of equations and are the driving motivation for randomized methods. Furthermore, we show that the low-rank approximations computed by these randomized algorithms are actually rank-revealing approximations, and the special case of a rank-1 approximation can also be used to correctly estimate matrix 2-norms with very high probability. Our numerical experiments are in full support of our conclusions.
Recommendations
- Subspace iteration method for generalized singular values
- Approximating matrix eigenvalues by subspace iteration with repeated random sparsification
- Subspace iterative methods for eigenvalue problems
- Randomized generalized singular value decomposition
- Randomized iterative methods for linear systems
- Iterative algorithms for computing the singular subspace of a matrix associated with its smallest singular values
- scientific article; zbMATH DE number 997682
- Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
- Norms of random submatrices and sparse approximation
- scientific article; zbMATH DE number 3909629
Cites work
- scientific article; zbMATH DE number 194139 (Why is no real title available?)
- scientific article; zbMATH DE number 3602632 (Why is no real title available?)
- scientific article; zbMATH DE number 1049347 (Why is no real title available?)
- scientific article; zbMATH DE number 1161558 (Why is no real title available?)
- scientific article; zbMATH DE number 781814 (Why is no real title available?)
- scientific article; zbMATH DE number 846277 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A Shifted Block Lanczos Algorithm for Solving Sparse Symmetric Generalized Eigenproblems
- A Survey of Condition Number Estimation for Triangular Matrices
- A fast and efficient algorithm for low-rank approximation of a matrix
- A fast direct solver for elliptic problems on general meshes in 2D
- A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- A fast randomized algorithm for overdetermined linear least-squares regression
- A fast randomized algorithm for the approximation of matrices
- A randomized algorithm for principal component analysis
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- ARPACK Users' Guide
- An efficient total least squares algorithm based on a rank-revealing two- sided orthogonal decomposition
- An implicit restarted Lanczos method for large symmetric eigenvalue problems
- An improved approximation algorithm for the column subset selection problem
- Applications of statistical condition estimation to the solution of linear systems
- Computing smallest singular triplets with implicitly restarted Lanczos bidiagonalization
- Condition Estimates
- Condition Numbers of Gaussian Random Matrices
- Dense Fast Random Projections and Lean Walsh Transforms
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Estimating the matrix p-norm
- Experience with a Matrix Norm Estimator
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Fast monte-carlo algorithms for finding low-rank approximations
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Implementation Aspects of Band Lanczos Algorithms for Computation of Eigenvalues of Large Sparse Symmetric Matrices
- Lanczos Algorithms for Large Symmetric Eigenvalue Computations
- Low-rank revealing \(UTV\) decompositions
- Methods of conjugate gradients for solving linear systems
- New efficient and robust HSS Cholesky factorization of SPD matrices
- Numerical methods for large eigenvalue problems
- On Rank-Revealing Factorisations
- On the Compression of Low Rank Matrices
- On the complexity of computing error bounds
- On the existence and computation of rank-revealing LU factorizations
- Preconditioned conjugate gradient methods. Proceedings of a conference held in Nijmegen, The Netherlands, June 19-21, 1989
- Principal component analysis.
- Probabilistic Bounds on the Extremal Eigenvalues and Condition Number by the Lanczos Algorithm
- Randomized Algorithms for Matrices and Data
- Randomized algorithms for the low-rank approximation of matrices
- Rang revealing QR factorizations
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- Regularization with randomized SVD for large-scale discrete inverse problems
- Relative-Error CUR Matrix Decompositions
- Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices
- Singular Value Decomposition, Eigenfaces, and 3D Reconstructions
- Some Applications of the Rank Revealing QR Factorization
- Strong rank revealing LU factorizations
- Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- Templates for the Solution of Algebraic Eigenvalue Problems
- The Evolution of the Minimum Degree Ordering Algorithm
- The University of Florida sparse matrix collection
- The variation of the spectrum of a normal matrix
- Thick-restart Lanczos method for large symmetric eigenvalue problems
- Updating a Rank-Revealing ULV Decomposition
- Using Linear Algebra for Intelligent Information Retrieval
Cited in
(73)- A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization?
- Singular values of dual quaternion matrices and their low-rank approximations
- Randomized algorithm for constrained quaternion singular value decomposition and its applications
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- An efficient algorithm for computing the approximate t-URV and its applications
- Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems
- Single-pass randomized QLP decomposition for low-rank approximation
- Regularized Linear Inversion with Randomized Singular Value Decomposition
- A randomized exponential canonical correlation analysis method for data analysis and dimensionality reduction
- Randomized QLP decomposition
- Randomized block Krylov methods for approximating extreme eigenvalues
- SVD-based algorithms for fully-connected tensor network decomposition
- Randomized core reduction for discrete ill-posed problem
- Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation
- Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Admissible subspaces and the subspace iteration method
- Randomized numerical linear algebra: Foundations and algorithms
- Low-rank approximation algorithm using sparse projection and its applications
- Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
- ALORA: affine low-rank approximations
- Algorithm-agnostic low-rank approximation of operator monotone matrix functions
- Randomized matrix-free trace and log-determinant estimators
- Randomized complete pivoting for solving symmetric indefinite linear systems
- Dynamically Orthogonal Runge–Kutta Schemes with Perturbative Retractions for the Dynamical Low-Rank Approximation
- Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
- Accurate low-rank approximations via a few iterations of alternating least squares
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Two-sided randomized algorithms for approximate \(K\)-term t-SVD
- Randomized algorithms for symmetric nonnegative matrix factorization
- Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition
- Conservatism of randomized structured singular value
- Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations
- Improvements to SLEPc in releases 3.14--3.18
- Faster noisy power method
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- Dominant subspace and low-rank approximations from block Krylov subspaces without a prescribed gap
- Bayesian D-optimal experimental designs via column subset selection
- Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
- Practical sketching algorithms for low-rank matrix approximation
- Joint randomized algorithms for the federated low-multilinear-rank approximation of modified Tucker decomposition
- A literature survey of matrix methods for data science
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- Randomized methods for matrix computations
- Subspaces analysis for random projection UTV framework
- SVD-based algorithms for tensor wheel decomposition
- Randomized quaternion QLP decomposition for low-rank approximation
- Matrix perturbation analysis of methods for extracting singular values from approximate singular subspaces
- Accuracy of singular vectors obtained by projection-based SVD methods
- Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization
- Sharp error bounds for approximate eigenvalues and singular values from subspace methods
- Randomized Dynamic Mode Decomposition
- Single-pass randomized algorithms for LU decomposition
- Analytical low-rank compression via proxy point selection
- An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
- A simple spectral algorithm for recovering planted partitions
- A fast contour-integral eigensolver for non-Hermitian matrices
- An incremental randomized algorithm for singular value decomposition of streaming data matrices
- Efficient bounds and estimates for canonical angles in randomized subspace approximations
- Norms of random submatrices and sparse approximation
- Literature survey on low rank approximation of matrices
- scientific article; zbMATH DE number 6860845 (Why is no real title available?)
- Low-rank approximation: randomized QR with column pivoting and related methods using sparse projection and pass-efficient techniques
- Estimating the largest elements of a matrix
- Error analysis of randomized symplectic model order reduction for Hamiltonian systems
- Approximating matrix eigenvalues by subspace iteration with repeated random sparsification
- Iterative algorithms for computing the singular subspace of a matrix associated with its smallest singular values
- Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
- Randomized algorithms for low-rank matrix factorizations: sharp performance bounds
- Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
- Pass-efficient truncated UTV for low-rank approximations
- Efficient algorithms for Tucker decomposition via approximate matrix multiplication
- Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
Describes a project that uses
Uses Software
This page was built for publication: Subspace Iteration Randomization and Singular Value Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5254699)
