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
- 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
- Condition Numbers of Gaussian Random Matrices
- CUR matrix decompositions for improved data analysis
- 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
- scientific article; zbMATH DE number 1049347 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
- LU factorization with panel rank revealing pivoting and its communication avoiding version
- 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
(7)- Random perturbation of low rank matrices: improving classical bounds
- On the accuracy of cross and column low-rank maxvol approximations in average
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- Error analysis of randomized symplectic model order reduction for Hamiltonian systems
- On the randomized multiple row-action methods for solving linear least-squares problems
- On the alternating randomized row-action methods with the application to data fitting
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)
