论文标题
低级别近似值，$ 1/ε^{1/3} $ matrix-vector产品
Low-Rank Approximation with $1/ε^{1/3}$ Matrix-Vector Products
论文作者
论文摘要
我们研究基于Krylov子空间的迭代方法，用于在任何Schatten $ p $ Norm中的低级别近似值。在这里，通过矩阵向量产品访问矩阵$ a $，精度参数$ε$和目标等级$ k $，目标是找到一个rank-$ k $矩阵$ z $，带有正顺列，以便$ \ | | a（i -zz^\ top）\ | _ {s_p} \ leq（1+ε）\ min_ { $ m $。对于$ p = 2 $（frobenius norm）和$ p = \ infty $（光谱规范）的特殊情况，Musco和Musco（Neurips 2015）获得了基于Krylov方法的算法，该方法使用了$ \ tilde {o}（o}（o）可通过功率方法获得的依赖性，其中$ \ tilde {o} $抑制了poly $（\ log（dk/ε））$因子。 我们的主要结果是一种仅使用$ \ tilde {o}（kp^{1/6}/ε^{1/3}）$ matrix-vector产品，并且适用于所有$ p \ geq 1 $的算法。对于$ p = 2 $，我们的界限改进了前一个$ \ tilde {o}（k/ε^{1/2}）$绑定到$ \ tilde {o}（k/ε^{1/3}）$。由于Schatten- $ p $和Schatten-$ \ infty $ norms的规范与$（1+ε）$相同 - 当$ p \ geq（\ log d）/ε$时，我们的限制恢复了Musco和Musco的结果$ p = \ infty $。此外，对于任何固定常数$ p \ geq 1 $，我们证明了$ω（1/ε^{1/3}）$的矩阵向量查询下限，表明令人惊讶的是$ \tildeθ（1/ε^{1/3}）$是常数〜$ k $的最佳复杂性。 为了获得我们的结果，我们介绍了几种新技术，包括同时对多个Krylov子空间进行优化，以及针对分区操作员的不平等现象。我们在[1,2] $中以$ p \的限制使用了Araki-lieb-thirring Trace不平等，而对于$ p> 2 $，我们呼吁对一致的分区操作员造成标准压缩不平等。
We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Here, given access to a matrix $A$ through matrix-vector products, an accuracy parameter $ε$, and a target rank $k$, the goal is to find a rank-$k$ matrix $Z$ with orthonormal columns such that $\| A(I -ZZ^\top)\|_{S_p} \leq (1+ε)\min_{U^\top U = I_k} \|A(I - U U^\top)\|_{S_p}$, where $\|M\|_{S_p}$ denotes the $\ell_p$ norm of the the singular values of $M$. For the special cases of $p=2$ (Frobenius norm) and $p = \infty$ (Spectral norm), Musco and Musco (NeurIPS 2015) obtained an algorithm based on Krylov methods that uses $\tilde{O}(k/\sqrtε)$ matrix-vector products, improving on the naïve $\tilde{O}(k/ε)$ dependence obtainable by the power method, where $\tilde{O}$ suppresses poly$(\log(dk/ε))$ factors. Our main result is an algorithm that uses only $\tilde{O}(kp^{1/6}/ε^{1/3})$ matrix-vector products, and works for all $p \geq 1$. For $p = 2$ our bound improves the previous $\tilde{O}(k/ε^{1/2})$ bound to $\tilde{O}(k/ε^{1/3})$. Since the Schatten-$p$ and Schatten-$\infty$ norms are the same up to a $(1+ ε)$-factor when $p \geq (\log d)/ε$, our bound recovers the result of Musco and Musco for $p = \infty$. Further, we prove a matrix-vector query lower bound of $Ω(1/ε^{1/3})$ for any fixed constant $p \geq 1$, showing that surprisingly $\tildeΘ(1/ε^{1/3})$ is the optimal complexity for constant~$k$. To obtain our results, we introduce several new techniques, including optimizing over multiple Krylov subspaces simultaneously, and pinching inequalities for partitioned operators. Our lower bound for $p \in [1,2]$ uses the Araki-Lieb-Thirring trace inequality, whereas for $p>2$, we appeal to a norm-compression inequality for aligned partitioned operators.
