Matrix-Vector Complexity of Low-Rank Approximation

Abstract

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+\epsilon$ times optimal. Write $N=\min \{m,n\}$ and let $Q_p^{\ast }$ denote the worst-case query budget for success probability $2/3$ on every input. For every $1\le k<N$ and sufficiently small $\epsilon$, our lower bounds, combined with existing Krylov upper bounds, give $Q_p^{\ast }=\tilde{\Theta }\left(\min \{N,k\min \{p^{1/6}{\epsilon }^{-1/3},{\epsilon }^{-1/2}\}\}\right)$ $(2\le p<\infty )$, $Q_{\infty }^{\ast }=\tilde{\Theta }\left(\min \{N,k{\epsilon }^{-1/2}\}\right)$. These bounds have universal constants and allow $p$ to vary with the problem parameters, identifying the transition at $p\epsilon \asymp 1$. A complementary result for each fixed $1\le p<2$ gives ${\tilde{\Theta }}_p(\min \{N,k{\epsilon }^{-1/3}\})$, with constants and an accuracy threshold that may depend on $p$. Together, the results recover this fixed-norm rate for every fixed finite $p$, supplying the multiplicative rank dependence missing from previous lower bounds. Tildes suppress logarithmic factors. The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace. Posterior overlap gives a short fixed-norm argument, while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint. Exact range recovery handles target costs of order $k$; the Wishart family covers the remaining regimes.