論文の概要: 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$ の場合、整列分割作用素に対するノルム圧縮不等式に訴える。
関連論文リスト
- Optimal Embedding Dimension for Sparse Subspace Embeddings [13.387361384552484]
ランダム$mtimes n$ matrix $S$は、忘れられない部分空間埋め込み(OSE)である。
mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$。
これを使用すれば、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
論文 参考訳(メタデータ) (2023-11-17T18:01:58Z) - Quantum and classical query complexities of functions of matrices [0.0]
任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
論文 参考訳(メタデータ) (2023-11-13T00:45:41Z) - Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。
我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
論文 参考訳(メタデータ) (2023-04-06T16:15:19Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳(メタデータ) (2022-09-30T04:15:44Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳(メタデータ) (2021-11-09T00:20:01Z) - Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank
Approximation [0.0]
カラムサブセット選択をベースとした$ell_p$ローランク近似アルゴリズムで$tildeO(k)$カラムをサンプリングする。
我々は、カラム部分集合選択に基づく$ell_p$低階近似を1p2$で厳密な上限と下限を得るように、結果を拡張した。
論文 参考訳(メタデータ) (2020-07-20T17:50:30Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳(メタデータ) (2020-05-22T16:55:01Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳(メタデータ) (2020-04-16T22:57:06Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。