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 (16)

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 ⋮ 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 ⋮ Linear-time CUR approximation of BEM matrices ⋮ 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

• LAPACK
• RSVDPACK
• rCUR

Cites Work

• 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
• Unnamed Item
• Unnamed Item

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