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.
翻译:在矩阵-向量乘积模型下,我们考虑了在各种Schatten范数下的秩为1的低秩近似问题:$$ \min_{\|u\|_2=1} \|A (I - u u^\top)\|_{\mathcal{S}_p} , $$ 其中 $\|M\|_{\mathcal{S}_p}$ 表示 $M$ 的奇异值的 $\ell_p$ 范数。给定 $\varepsilon>0$,我们的目标是输出一个单位向量 $v$,使得 $$ \|A(I - vv^\top)\|_{\mathcal{S}_p} \leq (1+\varepsilon) \min_{\|u\|_2=1}\|A(I - u u^\top)\|_{\mathcal{S}_p}. $$ 我们的主要结果显示,对于谱($p=\infty$),弗罗贝尼乌斯($p=2$)和核($p=1$)LRA,Krylov方法(几乎)实现了信息理论上的最优矩阵-向量乘积数量。尤其是,对于谱LRA,我们展示了任何算法都需要 $\Omega\left(\log(n)/\varepsilon^{1/2}\right)$ 矩阵-向量乘积,这与Krylov方法 [MM15, BCW22] 获得的上界完全匹配。我们的下界回答了 [Woo14] 中的开放问题1,为鉴别谱LRA算法缺乏进展提供了证据,并解决了[BCW22]中的开放问题1.2。接下来,我们展示,对于任何固定常数 $p$,即 $1\leq p=O(1)$,都存在 $O\left(\log(1/\varepsilon)/\varepsilon^{1/3}\right)$ 的矩阵-向量乘积上界,这意味着复杂度不随输入大小而增长。这改进了最近在[BCW22]中获得的 $O\left(\log(n/\varepsilon)/\varepsilon^{1/3}\right)$ 上界,并匹配了他们的 $\Omega\left(1/\varepsilon^{1/3}\right)$ 下界,还少了一个 $\log(1/\varepsilon)$ 的因子。