Fugu-MT 論文翻訳(概要): Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products

論文の概要: Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products

arxiv url: http://arxiv.org/abs/2202.05120v1
Date: Thu, 10 Feb 2022 16:10:41 GMT
ステータス: 処理完了
システム内更新日: 2022-02-11 19:42:19.694047
Title: Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products
Title（参考訳）: 1/\epsilon^{1/3}$行列ベクトル積による低位近似
Authors: Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff
Abstract要約: 我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
参考スコア（独自算出の注目度）: 58.05771390012827
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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 $\epsilon$, 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+\epsilon)\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{\epsilon})$ matrix-vector products, improving on the na\"ive $\tilde{O}(k/\epsilon)$ dependence obtainable by the power method, where $\tilde{O}$ suppresses poly$(\log(dk/\epsilon))$ factors. Our main result is an algorithm that uses only $\tilde{O}(kp^{1/6}/\epsilon^{1/3})$ matrix-vector products, and works for all $p \geq 1$. For $p = 2$ our bound improves the previous $\tilde{O}(k/\epsilon^{1/2})$ bound to $\tilde{O}(k/\epsilon^{1/3})$. Since the Schatten-$p$ and Schatten-$\infty$ norms are the same up to a $1+ \epsilon$ factor when $p \geq (\log d)/\epsilon$, our bound recovers the result of Musco and Musco for $p = \infty$. Further, we prove a matrix-vector query lower bound of $\Omega(1/\epsilon^{1/3})$ for any fixed constant $p \geq 1$, showing that surprisingly $\tilde{\Theta}(1/\epsilon^{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.
Abstract（参考訳）: 任意のシャッテン=p$ノルムの下で低ランク近似のためのクリロフ部分空間に基づく反復的手法について検討する。ここで、行列 $A$ が行列ベクトル積を通してアクセスされ、精度パラメータ $\epsilon$ とターゲットランク $k$ が与えられると、ゴールは、$\| A(I - ZZ^\top)\|_{S_p} \leq (1+\epsilon)\min_{U^\top U = I_k} \|A(I - U U U^\top)\|_{S_p}$ であるような正則列を持つランク-$k$ 行列 $Z$ を見つけることである。 p=2$ (frobenius norm) と $p = \infty$ (spectral norm) の特別な場合に対し、musco と musco (neurips 2015) は $\tilde{o}(k/\sqrt{\epsilon})$ matrix-vector 製品を使ったクライロフ法に基づくアルゴリズムを取得し、na\"ive $\tilde{o}(k/\epsilon)$ をパワー法で取得可能とし、$\tilde{o}$ は poly$(\log(dk/\epsilon))$ 因子を抑圧する。主な結果は、$\tilde{o}(kp^{1/6}/\epsilon^{1/3})$ matrix-vector積のみを使用し、すべての$p \geq 1$で動作するアルゴリズムである。 p = 2$ であれば、以前の$\tilde{o}(k/\epsilon^{1/2})$ を$\tilde{o}(k/\epsilon^{1/3})$ に改良する。 schatten-$p$ と schatten-$\infty$ のノルムは、$p \geq (\log d)/\epsilon$ のとき 1 + \epsilon$ となるので、我々のバウンドは、musco と musco の結果を$p = \infty$ で回復する。さらに、任意の固定定数$p \geq 1$に対して$\Omega(1/\epsilon^{1/3})$の行列ベクトルクエリローバウンドを証明し、驚くほど$\tilde{\Theta}(1/\epsilon^{1/3})$が定数~$k$の最適複雑性であることを示す。本研究では,複数のkrylov部分空間を同時に最適化し,分割作用素に対する不等式をピンチする手法を提案する。 p \in [1,2]$ に対する下限はアラキ-lieb-thirring トレース不等式を用いるが、$p>2$ の場合、整列分割作用素に対するノルム圧縮不等式に訴える。

論文の概要: Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products

関連論文リスト