An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
From MaRDI portal
Abstract: We introduce a Generalized LU-Factorization ( extbf{GLU}) for low-rank matrix approximation. We relate this to past approaches and extensively analyze its approximation properties. The established deterministic guarantees are combined with sketching ensembles satisfying Johnson-Lindenstrauss properties to present complete bounds. Particularly good performance is shown for the sub-sampled randomized Hadamard transform (SRHT) ensemble. Moreover, the factorization is shown to unify and generalize many past algorithms. It also helps to explain the effect of sketching on the growth factor during Gaussian Elimination.
Cites work
- scientific article; zbMATH DE number 1049347 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- A Generalization of the Schur Complement by Means of the Moore–Penrose Inverse
- Adaptive estimation of a quadratic functional by model selection.
- An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems
- Average-Case Stability of Gaussian Elimination
- CUR matrix decompositions for improved data analysis
- Condition Numbers of Gaussian Random Matrices
- Dimensionality reduction for k-means clustering and low rank approximation
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Fast linear algebra is stable
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- LU factorization with panel rank revealing pivoting and its communication avoiding version
- Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
- Maxima of entries of Haar distributed matrices
- Optimal Approximate Matrix Product in Terms of Stable Rank
- Practical sketching algorithms for low-rank matrix approximation
- Randomized LU decomposition
- Randomized numerical linear algebra: Foundations and algorithms
- Revisiting the Nyström method for improved large-scale machine learning
- Sketching as a tool for numerical linear algebra
- Smallest eigenvalue distributions for two classes of {\(\beta\)}-Jacobi ensembles
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Strong rank revealing LU factorizations
- Subspace Iteration Randomization and Singular Value Problems
- Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods
Cited in
(6)- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- On the accuracy of cross and column low-rank maxvol approximations in average
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- Random perturbation of low rank matrices: improving classical bounds
- On the randomized multiple row-action methods for solving linear least-squares problems
- Error analysis of randomized symplectic model order reduction for Hamiltonian systems
This page was built for publication: An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6101124)
