論文の概要: Krylov Methods are (nearly) Optimal for Low-Rank Approximation
- arxiv url: http://arxiv.org/abs/2304.03191v1
- Date: Thu, 6 Apr 2023 16:15:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-07 13:33:38.760486
- Title: Krylov Methods are (nearly) Optimal for Low-Rank Approximation
- Title（参考訳）: Krylov法は(ほぼ)低ランク近似に最適である
- Authors: Ainesh Bakshi and Shyam Narayanan
- Abstract要約: 任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。
我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
- 参考スコア（独自算出の注目度）: 8.017116107657206
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
- Abstract（参考訳）: 様々なシャッテンノルムの下で行列ベクトル積モデルにおけるランク-1$ローランク近似(LRA)の問題を考える:$$$ \min_{\|u\|_2=1} \|A (I - u u^\top)\|_{\mathcal{S}_p}, $$$ ここで$\|M\|_{\mathcal{S}_p}$は$M$の特異値の$\ell_p$ノルムを表す。
我々のゴールは、$\varepsilon>0$を与えられたとき、$$ \|A(I - vv^\top)\|_{\mathcal{S}_p} \leq (1+\varepsilon) \min_{\|u\|_2=1}\|A(I - u u^\top)\|_{\mathcal{S}_p} となるような単位ベクトル $v$ を出力することである。
主な結果は、krylov法(ほぼ)がスペクトル(p=infty$)、フロベニウス(p=2$)、核(p=1$)lraの行列ベクトル生成物の情報理論上最適な数を達成することを示している。
特にスペクトル LRA の場合、任意のアルゴリズムが$\Omega\left(\log(n)/\varepsilon^{1/2}\right)$ matrix-vector product を必要とし、Krylov 法 [MM15, BCW22] によって得られる上限値と正確に一致することを示す。
我々の下位境界は[Woo14]のオープン質問1で、スペクトルLRAのアルゴリズムの進歩の欠如の証拠を提供し、[BCW22]のオープン質問1.2を解決します。
次に、任意の固定定数 $p$、すなわち $1\leq p =o(1)$ に対して、$o\left(\log(1/\varepsilon)/\varepsilon^{1/3}\right)$ matrix-vector の上限が存在し、これは複雑性が入力サイズの関数として成長しないことを意味する。
これにより、最近[bcw22]で得られた$o\left(\log(n/\varepsilon)/\varepsilon^{1/3}\right)$バウンドが改善され、その$\omega\left(1/\varepsilon^{1/3}\right)$下限値が$\log(1/\varepsilon)$ファクタに一致する。
関連論文リスト
- Fast, robust approximate message passing [2.668787455520979]
本稿では,AMPアルゴリズムを頑健に実装するための高速なスペクトル計算法を提案する。
提案アルゴリズムはスペクトル前処理のステップを実行し,$mathcal A$の摂動を緩やかに修正する。
論文 参考訳（メタデータ） (2024-11-05T03:20:14Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
ランダム$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) - Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products [9.661328973620531]
自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。
我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。
我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
論文 参考訳（メタデータ） (2023-11-03T14:56:24Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳（メタデータ） (2021-03-17T18:18:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。