Efficient algorithms for CUR and interpolative matrix decompositions

DOI10.1007/s10444-016-9494-8zbMath1369.65049arXiv1412.8447MaRDI QIDQ2363512

Per-Gunnar Martinsson, Sergey Voronin

Publication date: 19 July 2017

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

singular value decomposition; convergence acceleration; numerical experiment; QR decomposition; randomized algorithms; low rank approximation; interpolative decomposition; \(\mathsf CUR\) factorizations

Mathematics Subject Classification ID

65F20: Numerical solutions to overdetermined systems, pseudoinverses

65F05: Direct numerical methods for linear systems and matrix inversion

Related Items

ALORA: affine low-rank approximations

Uses Software

• LAPACK
• RSVDPACK
• rCUR

Cites Work

• 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 algorithm for the inversion of general Toeplitz matrices
• A fast randomized algorithm for the approximation of matrices
• A theory of pseudoskeleton approximations
• Incomplete cross approximation in the mosaic-skeleton method
• A DEIM Induced CUR Factorization
• Optimal CUR Matrix Decompositions
• Randomized algorithms for the low-rank approximation of matrices
• A Randomized Algorithm for Principal Component Analysis
• Relative-Error $CUR$ Matrix Decompositions
• LAPACK Users' Guide
• The Hat Matrix in Regression and ANOVA
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization