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
- 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 Shifted Block Lanczos Algorithm for Solving Sparse Symmetric Generalized Eigenproblems
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- A Survey of Condition Number Estimation for Triangular Matrices
- 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
- ARPACK Users' Guide
- 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
- 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?)
- 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 complexity of computing error bounds
- On the Compression of Low Rank Matrices
- 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
(77)- Iterative algorithms for computing the singular subspace of a matrix associated with its smallest singular values
- Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations
- A simple spectral algorithm for recovering planted partitions
- Accuracy of singular vectors obtained by projection-based SVD methods
- A randomized exponential canonical correlation analysis method for data analysis and dimensionality reduction
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- Randomized block Krylov methods for approximating extreme eigenvalues
- Single-pass randomized QLP decomposition for low-rank approximation
- Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems
- Randomized quaternion QLP decomposition for low-rank approximation
- An efficient algorithm for computing the approximate t-URV and its applications
- Randomized QLP decomposition
- A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization?
- Single-pass randomized algorithms for LU decomposition
- Randomized core reduction for discrete ill-posed problem
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- ALORA: affine low-rank approximations
- Randomized algorithms for low-rank matrix factorizations: sharp performance bounds
- Norms of random submatrices and sparse approximation
- Randomized matrix-free trace and log-determinant estimators
- Estimating the largest elements of a matrix
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
- Randomized complete pivoting for solving symmetric indefinite linear systems
- Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization
- A fast contour-integral eigensolver for non-Hermitian matrices
- Practical sketching algorithms for low-rank matrix approximation
- Literature survey on low rank approximation of matrices
- Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
- scientific article; zbMATH DE number 6860845 (Why is no real title available?)
- Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
- Approximating matrix eigenvalues by subspace iteration with repeated random sparsification
- Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation
- Subspaces analysis for random projection UTV framework
- Singular values of dual quaternion matrices and their low-rank approximations
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
- Regularized Linear Inversion with Randomized Singular Value Decomposition
- Randomized methods for matrix computations
- Analytical low-rank compression via proxy point selection
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- Randomized Dynamic Mode Decomposition
- Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
- Conservatism of randomized structured singular value
- Accurate low-rank approximations via a few iterations of alternating least squares
- Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
- Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition
- Randomized numerical linear algebra: Foundations and algorithms
- Dynamically Orthogonal Runge–Kutta Schemes with Perturbative Retractions for the Dynamical Low-Rank Approximation
- A literature survey of matrix methods for data science
- An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
- Pass-efficient truncated UTV for low-rank approximations
- Admissible subspaces and the subspace iteration method
- SVD-based algorithms for fully-connected tensor network decomposition
- Two-sided randomized algorithms for approximate \(K\)-term t-SVD
- Improvements to SLEPc in releases 3.14--3.18
- SVD-based algorithms for tensor wheel decomposition
- Efficient bounds and estimates for canonical angles in randomized subspace approximations
- Joint randomized algorithms for the federated low-multilinear-rank approximation of modified Tucker decomposition
- Sharp error bounds for approximate eigenvalues and singular values from subspace methods
- An incremental randomized algorithm for singular value decomposition of streaming data matrices
- Matrix perturbation analysis of methods for extracting singular values from approximate singular subspaces
- Low-rank approximation: randomized QR with column pivoting and related methods using sparse projection and pass-efficient techniques
- Error analysis of randomized symplectic model order reduction for Hamiltonian systems
- Randomized algorithm for constrained quaternion singular value decomposition and its applications
- Efficient algorithms for Tucker decomposition via approximate matrix multiplication
- Low-rank approximation algorithm using sparse projection and its applications
- Randomized algorithms for symmetric nonnegative matrix factorization
- Faster noisy power method
- Dominant subspace and low-rank approximations from block Krylov subspaces without a prescribed gap
- Algorithm-agnostic low-rank approximation of operator monotone matrix functions
- Bayesian D-optimal experimental designs via column subset selection
- Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
- A power method for computing singular value decomposition
- Adaptive, Matrix-Free Low-Rank Approximation
- Randomized structured total-least-squares-based higher-order extended dynamic mode decomposition
- Spectral Deflation for Factorization-Free Matrix Filtering in Muon and Semidefinite Programming
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)
