Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
From MaRDI portal
Abstract: This paper is concerned with approximating the dominant left singular vector space of a real matrix of arbitrary dimension, from block Krylov spaces generated by the matrix and the block vector . Two classes of results are presented. First are bounds on the distance, in the two and Frobenius norms, between the Krylov space and the target space. The distance is expressed in terms of principal angles. Second are quality of approximation bounds, relative to the best approximation in the Frobenius norm. For starting guesses of full column-rank, the bounds depend on the tangent of the principal angles between and the dominant right singular vector space of . The results presented here form the structural foundation for the analysis of randomized Krylov space methods. The innovative feature is a combination of traditional Lanczos convergence analysis with optimal approximations via least squares problems.
Recommendations
- Convergence properties of some block Krylov subspace methods for multiple linear systems
- Strong convergence of almost simultaneous block-iterative projection methods in Hilbert spaces
- A priori error bounds on invariant subspace approximations by block Krylov subspaces
- Convergence of block iterative methods applied to sparse least-squares problems
- Convergence analysis of Krylov subspace methods
- Block Krylov subspace methods for functions of matrices
- Block Krylov subspace methods for approximating the linear combination of \(\varphi\)-functions arising in exponential integrators
- On the convergence of Krylov subspace methods for matrix Mittag-Leffler functions
- Convergence Analysis of Krylov Subspace Iterations with Methods from Potential Theory
- Convergence theorems for block splitting iterative methods for linear systems
Cites work
- A fast and efficient algorithm for low-rank approximation of a matrix
- Angles between subspaces and their tangents
- Augmented Implicitly Restarted Lanczos Bidiagonalization Methods
- Computation of generalized matrix functions
- Convergence of Polynomial Restart Krylov Methods for Eigenvalue Computations
- Convergence of Restarted Krylov Subspaces to Invariant Subspaces
- Convergence of the block Lanczos method for eigenvalue clusters
- Estimating Extremal Eigenvalues and Condition Numbers of Matrices
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Faster least squares approximation
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 52076 (Why is no real title available?)
- scientific article; zbMATH DE number 194139 (Why is no real title available?)
- scientific article; zbMATH DE number 766233 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- Improved analysis of the subsampled randomized Hadamard transform
- Improving the Accuracy of Inverse Iteration
- Low rank matrix-valued Chernoff bounds and approximate matrix multiplication
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications
- Near Optimal Column-Based Matrix Reconstruction
- Near-optimal column-based matrix reconstruction
- Numerical methods for large eigenvalue problems
- Numerical methods in matrix computations
- On generalized matrix functions
- On relative residual bounds for the eigenvalues of a Hermitian matrix
- On the Rates of Convergence of the Lanczos and the Block-Lanczos Methods
- Probabilistic Bounds on the Extremal Eigenvalues and Condition Number by the Lanczos Algorithm
- Relative-Error CUR Matrix Decompositions
- Restarted block Lanczos bidiagonalization methods
- Sketching as a tool for numerical linear algebra
- Some norm inequalities concerning generalized inverses
- Subspace gap residuals for Rayleigh-Ritz approximations
- Subspace Iteration Randomization and Singular Value Problems
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
Cited in
(21)- Randomized block Krylov subspace methods for trace and log-determinant estimators
- Randomized block Krylov methods for approximating extreme eigenvalues
- Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
- A probabilistic subspace bound with application to active subspaces
- Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Uniform Error Estimates for the Lanczos Method
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- Sketching for principal component regression
- A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
- Krylov-Aware Stochastic Trace Estimation
- Admissible subspaces and the subspace iteration method
- Sharp Majorization-Type Cluster Robust Bounds for Block Filters and Eigensolvers
- Randomized block Krylov subspace algorithms for low-rank quaternion matrix approximations
- SVD-based algorithms for fully-connected tensor network decomposition
- SVD-based algorithms for tensor wheel decomposition
- Solution of large linear discrete ill-posed problems by randomized block Krylov methods
- Randomized algorithm for constrained quaternion singular value decomposition and its applications
- Randomized low-rank approximations beyond Gaussian random matrices
- Dominant subspace and low-rank approximations from block Krylov subspaces without a prescribed gap
- Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
This page was built for publication: Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5373926)
