Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
From MaRDI portal
Publication:6052452
DOI10.1007/s10444-023-10061-zMaRDI QIDQ6052452
Per-Gunnar Martinsson, Yijun Dong
Publication date: 22 September 2023
Published in: Advances in Computational Mathematics (Search for Journal in Brave)
low-rank approximationinterpolative decompositionrank revealing factorizationCUR decompositionrandomized numerical linear algebracolumn pivoted QR factorization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
- CUR matrix decompositions for improved data analysis
- Rang revealing QR factorizations
- A fast randomized algorithm for the approximation of matrices
- On selecting a maximum volume sub-matrix of a matrix and related problems
- A theory of pseudoskeleton approximations
- Incomplete cross approximation in the mosaic-skeleton method
- On the existence and computation of rank-revealing LU factorizations
- Approximation of boundary element matrices
- Randomized LU decomposition
- Strong rank revealing LU factorizations
- Exponential inapproximability of selecting a maximum volume sub-matrix
- Randomized LU decomposition using sparse projections
- Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
- Numerically safe Gaussian elimination with no pivoting
- Efficient algorithms for CUR and interpolative matrix decompositions
- Invertibility of random matrices: norm of the inverse
- A New Selection Operator for the Discrete Empirical Interpolation Method---Improved A Priori Error Bound and Extensions
- A DEIM Induced CUR Factorization
- Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform
- Computational Advertising: Techniques for Targeting Relevant Ads
- Optimal CUR Matrix Decompositions
- Uniform Sampling for Matrix Approximation
- Randomized algorithms for the low-rank approximation of matrices
- A fast randomized algorithm for overdetermined linear least-squares regression
- IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
- Low-Rank Approximation and Regression in Input Sparsity Time
- CALU: A Communication Optimal LU Factorization Algorithm
- Average-Case Stability of Gaussian Elimination
- Relative-Error $CUR$ Matrix Decompositions
- $LU$ Factorization Algorithms on Distributed-Memory Multiprocessor Architectures
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- On the stability of Gauss-Jordan elimination with pivoting
- Practical Sketching Algorithms for Low-Rank Matrix Approximation
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
- Determinantal Point Processes in Randomized Numerical Linear Algebra
- Twice-ramanujan sparsifiers
- Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
- Near-Optimal Column-Based Matrix Reconstruction
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Numerical Linear Algebra
- Unitary Triangularization of a Nonsymmetric Matrix
- Randomized numerical linear algebra: Foundations and algorithms
