{"id":"arxiv/2610.03321","url":"https://arxiv.org/abs/2610.03321","tags":["math.OC","cs.AI","cs.IT"],"score":0,"title":"Information Limits of Low-Rank Approximation Certification","domain":"math.OC","source":"arxiv","authors":["Kang Liu","Bohao Qu"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}