arXiv：cs.AI· Kang Liu, Bohao Qu·· 4 小时前AI 评分36
低秩近似认证的信息极限
Information Limits of Low-Rank Approximation Certification
AI 导读
研究刻画了低秩近似认证所需矩阵-向量乘积查询成本，覆盖相对矩阵误差与均方输出误差两类目标。核心结果是：当候选族独立于验证集构建时，单批验证响应即可支撑整条嵌套路径，查询预算不随检查次数增长；跨 W 条路径时，利用共享残差能量的集中界给出 √log(W+1) 依赖，并配有匹配下界证明其最优性。在分散谱族上比较两种一致有效证书，验证与构建成本分别达到 N^{1/3} 和 N^{2/3} 量级。
正文
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 this https URL
| Subjects: | Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Information Theory (cs.IT) |
| Cite as: | arXiv:2610.03321 [math.OC] |
| (or arXiv:2610.03321v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.03321 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Kang Liu [view email]
[v1]
Fri, 2 Oct 2026 13:56:10 UTC (233 KB)
来源：arXiv：cs.AI · arxiv.org