{"id":"arxiv/2609.35840","url":"https://arxiv.org/abs/2609.35840","tags":["math.OC","cs.DS"],"score":0,"title":"Matrix-Vector Complexity of Low-Rank Approximation","domain":"math.OC","source":"arxiv","authors":["Haihan Zhang","Wendao Wu","Chenheng Zhang","Yanyi Li","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"We establish matching polynomial query bounds for low-rank approximation from exact matrix--vector products. Given an unknown matrix $A\\in\\mathbb{R}^{m\\times n}$, at each step a randomized algorithm chooses either $v\\in\\mathbb{R}^n$ and receives $Av$, or $u\\in\\mathbb{R}^m$ and receives $A^\\top u$. The choice may depend measurably on all previous queries and replies and on the algorithm's private randomness; each vector product costs one query. The output is a rank-$k$ right projector with Schatten-$p$ residual at most $1+\\varepsilon$ times optimal. Write $N=\\min\\{m,n\\}$ and let $Q_p^*$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{}}