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-squar