Blind error estimation for CUR approximation
Abstract
Low-rank approximation is a fundamental tool for scalable matrix computations. While such approximations have classically been formed via the truncated SVD, recent advances in randomized numerical linear algebra have produced methods of comparable accuracy at a fraction of the cost. A key advantage of these approaches is their ability to operate with limited access to the full matrix. A prominent example is the CUR decomposition, which builds an approximation from only a subset of columns and rows, making it particularly well-suited to settings where global matrix access is unavailable, such as in the design of spectro-microscopy experiments where even matrix-vector products cannot be computed. However, the randomness inherent to these methods introduces a key challenge: efficiently assessing approximation accuracy under the stringent constraint that only a subset of matrix entries can be observed. We derive a "blind" estimator of the Frobenius error of a CUR decomposition. For this estimator, we derive a worst-case lower bound on the number of required column queries, and provide techniques for quantifying its uncertainty. Finally, we demonstrate the performance of the estimator and the uncertainty sets on a mix of synthetic problems and real spectro-microscopy examples.
Related
- Residual-based a posteriori error estimate for a parareal approximation of the cardiac monodomain problem
- A posteriori error estimates for a finite volume approximation of a local sensing Keller-Segel model
- A statistical theory for blind denoising: minimax estimation of the noise level from a single sample
- Stable Rational Approximation of PDE Transfer Functions with H∞ Error Bounds
- When n is not enough: Assessing the interplay of spatial sampling error and sample selection in abundance estimation
BibTeX
@misc{lazzarino2026blind,
title = {{Blind error estimation for CUR approximation}},
author = {Lorenzo Lazzarino and Katherine J. Pearce and Nathaniel Pritchard},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23810},
eprint = {2609.23810},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23810},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Blind error estimation for CUR approximation
AU - Lorenzo Lazzarino
AU - Katherine J. Pearce
AU - Nathaniel Pritchard
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23810
UR - https://arxiv.org/abs/2609.23810
AB - Low-rank approximation is a fundamental tool for scalable matrix computations. While such approximations have classically been formed via the truncated SVD, recent advances in randomized numerical linear algebra have produced methods of comparable accuracy at a fraction of the cost. A key advantage of these approaches is their ability to operate with limited access to the full matrix. A prominent example is the CUR decomposition, which builds an approximation from only a subset of columns and rows, making it particularly well-suited to settings where global matrix access is unavailable, such as in the design of spectro-microscopy experiments where even matrix-vector products cannot be computed. However, the randomness inherent to these methods introduces a key challenge: efficiently assessing approximation accuracy under the stringent constraint that only a subset of matrix entries can be observed. We derive a "blind" estimator of the Frobenius error of a CUR decomposition. For this estimator, we derive a worst-case lower bound on the number of required column queries, and provide techniques for quantifying its uncertainty. Finally, we demonstrate the performance of the estimator and the uncertainty sets on a mix of synthetic problems and real spectro-microscopy examples.
ER -