Efficient algorithms for CUR and interpolative matrix decompositions

DOI10.1007/S10444-016-9494-8zbMath1369.65049arXiv1412.8447OpenAlexW2963297473MaRDI 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 decompositionconvergence accelerationnumerical experimentQR decompositionrandomized algorithmslow rank approximationinterpolative decomposition\(\mathsf CUR\) factorizations

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (24)

Randomized numerical linear algebra: Foundations and algorithms ⋮ A Generalized CUR Decomposition for Matrix Pairs ⋮ Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions ⋮ A literature survey of matrix methods for data science ⋮ Fast deflation sparse principal component analysis via subspace projections ⋮ Generalized pseudoskeleton decompositions ⋮ Randomized GCUR decompositions ⋮ A two-stage surrogate model for neo-Hookean problems based on adaptive proper orthogonal decomposition and hierarchical tensor approximation ⋮ Fast randomized matrix and tensor interpolative decomposition using countsketch ⋮ Fixed-precision randomized low-rank approximation methods for nonlinear model order reduction of large systems ⋮ Randomized low-rank approximation methods for projection-based model order reduction of large nonlinear dynamical problems ⋮ An L-DEIM induced high order tensor interpolatory decomposition ⋮ Block discrete empirical interpolation methods ⋮ Linear-time CUR approximation of BEM matrices ⋮ Broadband recursive skeletonization ⋮ The discrete empirical interpolation method in class identification and data summarization ⋮ Online randomized interpolative decomposition with \textit{a posteriori} error estimator for temporal PDE data reduction ⋮ Perspectives on CUR decompositions ⋮ ALORA: affine low-rank approximations ⋮ Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning ⋮ Unnamed Item ⋮ Perturbations of CUR Decompositions ⋮ Robust CUR Decomposition: Theory and Imaging Applications ⋮ LU and CR Elimination

Uses Software

• RSVDPACK
• rCUR
• Unnamed Item

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

This page was built for publication: Efficient algorithms for CUR and interpolative matrix decompositions