Blind error estimation for CUR approximation

DOI10.48550/arXiv.2609.23810MaRDI QIDQ7353445arXivFDO

Authors Lorenzo Lazzarino, Katherine J. Pearce, Nathaniel Pritchard

Publication date 20 September 2026

Published in arXiv

Tldr We design an efficient, "blind" error estimator for CUR approximations, which can assess accuracy without requiring full matrix access, providing worst-case guarantees and uncertainty bounds.

Full work available at URL https://doi.org/10.48550/arXiv.2609.23810

arXiv classification

math.NA

Cites work

• A DEIM induced CUR factorization
• A Generalization of Sampling Without Replacement From a Finite Universe
• A new selection operator for the discrete empirical interpolation method -- improved a priori error bound and extensions
• A theory of pseudoskeleton approximations
• Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation
• Bootstrap methods: another look at the jackknife
• Close to optimal column approximation using a single SVD
• CUR matrix decompositions for improved data analysis
• Efficient Error and Variance Estimation for Randomized Matrix Computations
• Efficient volume sampling for row/column subset selection
• Fast and stable randomized low-rank matrix approximation
• Fast Monte-Carlo algorithms for finding low-rank approximations
• Fast Rank Adaptive CUR via a Recycled Small Sketch
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
• Model assisted survey sampling
• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Rate of convergence to normal distribution for the Horvitz-Thompson estimator.
• Resampling Inference with Complex Survey Data
• Robust Blockwise Random Pivoting: Fast and Accurate Adaptive Interpolative Decomposition
• Solving, Tracking and Stopping Streaming Linear Inverse Problems
• The approximation of one matrix by another of lower rank.
• Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification

This page was built for publication: Blind error estimation for CUR approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7353445)