Information Limits of Low-Rank Approximation Certification

arXiv:2610.03321v1 Announce Type: cross 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 (sqrt{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/

Related

• ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers
• The Routing and Filtering Structure of Attention
• Sequential Functional Structured Tucker Compression for Large Language Model Attentions

Source: arXiv cs.AI | 2026-10-05