Information Limits of Low-Rank Approximation Certification
Abstract
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/
Related
- Sequential Certification of Partially Identified Product Targets: Information Limits and Adaptive Sampling
- On the Oja-Flow-Based Low-Rank Approximation of Kalman-Bucy Filters for Linear Time-Varying Systems
- Generic factorizations and alternating direction method for fixed-rank approximation of matrix polynomials
- Efficient Low-Rank Approximation of Quaternion Matrices via Adaptive Cross Approximation
- Convergence rates of randomly pivoted methods for low-rank approximation
BibTeX
@misc{liu2026information,
title = {{Information Limits of Low-Rank Approximation Certification}},
author = {Kang Liu and Bohao Qu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03321},
eprint = {2610.03321},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03321},
}
RIS
TY - UNPB
TI - Information Limits of Low-Rank Approximation Certification
AU - Kang Liu
AU - Bohao Qu
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03321
UR - https://arxiv.org/abs/2610.03321
AB - 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 N^1/3 and N^2/3 for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/
ER -