Krylov Methods are (nearly) Optimal for Low-Rank Approximation

We consider the problem of rank-1 low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms:equation_|u|_2=1|A(I-u u^)|_S_pequationwhere $\|M\|_{\mathcal{S}_{p}}$ denotes the $\ell_{p}$ norm of the singular values of M. Given $\varepsilon\gt 0$, our goal is to output a unit vector v such that equation*|A(I-v v^)|_S_p (1+) _|u|_2=1|A(I-u u^)|_S_pequation*Our main result shows that Krylov methods (nearly) achieve the information-theoretically optimal1number of matrix-vector products for Spectral $(p=\infty)$, Frobenius $(p=2)$ and Nuclear $(p=1)$ LRA. In particular, for Spectral LRA, we show that any algorithm requires $\Omega\left(\log (n) / \varepsilon^{1 / 2}\right)$ matrix-vector products, exactly matching the upper bound obtained by Krylov methods [40]. Our lower bound addresses Open Question 1 in [59], providing evidence for the lack of progress on algorithms for Spectral LRA and resolves Open Question 1.2 in [5]. Next, we show that for any fixed constant p, i.e. $1 \leqslant p=O(1)$, there is an upper bound of $O\left(\log (1 / \varepsilon) / \varepsilon^{1 / 3}\right)$ matrix-vector products, implying that the complexity does not grow as a function of input size. This improves the $O\left(\log (n / \varepsilon) / \varepsilon^{1 / 3}\right)$ bound recently obtained in [5], and matches their $\Omega\left(1 / \varepsilon^{1 / 3}\right)$ lower bound, to a $\log (1 / \varepsilon)$ factor.1For Spectral LRA, the upper and lower bounds match up to a fixed universal constant. For Frobenius and Nuclear LRA, they match up to a $\log (1 / \varepsilon)$ factor.