  We consider the problem of rank-$1$ low-rank approximation (LRA) in the
matrix-vector product model under various Schatten norms: $$
  \min_{\|u\|_2=1} \|A (I - u u^\top)\|_{\mathcal{S}_p} , $$ where
$\|M\|_{\mathcal{S}_p}$ denotes the $\ell_p$ norm of the singular values of
$M$. Given $\varepsilon>0$, our goal is to output a unit vector $v$ such that
$$
  \|A(I - vv^\top)\|_{\mathcal{S}_p} \leq (1+\varepsilon) \min_{\|u\|_2=1}\|A(I
- u u^\top)\|_{\mathcal{S}_p}. $$ Our main result shows that Krylov methods
(nearly) achieve the information-theoretically optimal number 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 [MM15, BCW22]. Our lower
bound addresses Open Question 1 in [Woo14], providing evidence for the lack of
progress on algorithms for Spectral LRA and resolves Open Question 1.2 in
[BCW22]. Next, we show that for any fixed constant $p$, i.e. $1\leq 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 [BCW22], and matches their
$\Omega\left(1/\varepsilon^{1/3}\right)$ lower bound, to a
$\log(1/\varepsilon)$ factor.
