An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation

DOI10.1137/21m1391316arXiv1910.00223OpenAlexW4376128757MaRDI QIDQ6101124

James W. Demmel, Alexander Rusciano, Laura Grigori

Publication date: 31 May 2023

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.00223

zbMATH Keywords

deterministic algorithmsrandomized algorithmslow-rank approximationkernel approximationspectrum preserving

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• CUR matrix decompositions for improved data analysis
• An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems
• Randomized LU decomposition
• Maxima of entries of Haar distributed matrices
• Adaptive estimation of a quadratic functional by model selection.
• Strong rank revealing LU factorizations
• Fast linear algebra is stable
• Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform
• LU Factorization with Panel Rank Revealing Pivoting and Its Communication Avoiding Version
• Smallest eigenvalue distributions for two classes of β-Jacobi ensembles
• Computational Advertising: Techniques for Targeting Relevant Ads
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Low-Rank Approximation and Regression in Input Sparsity Time
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Average-Case Stability of Gaussian Elimination
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Subspace Iteration Randomization and Singular Value Problems
• Condition Numbers of Gaussian Random Matrices
• A Generalization of the Schur Complement by Means of the Moore–Penrose Inverse
• Randomized numerical linear algebra: Foundations and algorithms