# Information Limits of Low-Rank Approximation Certification

arXiv: https://arxiv.org/abs/2610.03321 · HTML: https://mlsanity.com/paper/2610.03321/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 24 references that are in the map.
- First posted on arXiv 2 Oct 2026.

## Builds on (most cited first, 7 of 7)

- [Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation](https://mlsanity.com/paper/1404.0736/) (2014)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation](https://mlsanity.com/paper/1901.00555/) (2019)
- [Optimal query complexity for estimating the trace of a matrix](https://mlsanity.com/paper/1405.7112/) (2014)
- [Dynamic Trace Estimation](https://mlsanity.com/paper/2110.13752/) (2021)
- [Optimal Query Complexities for Dynamic Trace Estimation](https://mlsanity.com/paper/2209.15219/) (2022)
- [Efficient error and variance estimation for randomized matrix computations](https://mlsanity.com/paper/2207.06342/) (2022)

## Abstract (arXiv)

Low-rank approximation can require additional matrix--vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across (W) paths, a concentration bound exploiting shared residual energy yields a (√log(W+1)) dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders (N1/3) and (N2/3) for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/