論文の概要: Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products
- arxiv url: http://arxiv.org/abs/2311.01960v1
- Date: Fri, 3 Nov 2023 14:56:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-06 13:43:19.709809
- Title: Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products
- Title（参考訳）: 高度変換マトリックス製品の低ランク近似の硬さ
- Authors: Tamas Sarlos, Xingyou Song, David Woodruff, Qiuyi (Richard) Zhang
- Abstract要約: 自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。
我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。
我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
- 参考スコア（独自算出の注目度）: 9.661328973620531
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Inspired by fast algorithms in natural language processing, we study low rank
approximation in the entrywise transformed setting where we want to find a good
rank $k$ approximation to $f(U \cdot V)$, where $U, V^\top \in \mathbb{R}^{n
\times r}$ are given, $r = O(\log(n))$, and $f(x)$ is a general scalar
function. Previous work in sublinear low rank approximation has shown that if
both (1) $U = V^\top$ and (2) $f(x)$ is a PSD kernel function, then there is an
$O(nk^{\omega-1})$ time constant relative error approximation algorithm, where
$\omega \approx 2.376$ is the exponent of matrix multiplication. We give the
first conditional time hardness results for this problem, demonstrating that
both conditions (1) and (2) are in fact necessary for getting better than
$n^{2-o(1)}$ time for a relative error low rank approximation for a wide class
of functions. We give novel reductions from the Strong Exponential Time
Hypothesis (SETH) that rely on lower bounding the leverage scores of flat
sparse vectors and hold even when the rank of the transformed matrix $f(UV)$
and the target rank are $n^{o(1)}$, and when $U = V^\top$. Furthermore, even
when $f(x) = x^p$ is a simple polynomial, we give runtime lower bounds in the
case when $U \neq V^\top$ of the form $\Omega(\min(n^{2-o(1)}, \Omega(2^p)))$.
Lastly, we demonstrate that our lower bounds are tight by giving an $O(n \cdot
\text{poly}(k, 2^p, 1/\epsilon))$ time relative error approximation algorithm
and a fast $O(n \cdot \text{poly}(k, p, 1/\epsilon))$ additive error
approximation using fast tensor-based sketching. Additionally, since our low
rank algorithms rely on matrix-vector product subroutines, our lower bounds
extend to show that computing $f(UV)W$, for even a small matrix $W$, requires
$\Omega(n^{2-o(1)})$ time.
- Abstract（参考訳）: 自然言語処理における高速なアルゴリズムに触発されて、エントリワイズ変換された設定において、低ランク近似(英語版)(low rank approximation)を研究し、良いランクの$k$近似を$f(u \cdot v)$、ここで$u, v^\top \in \mathbb{r}^{n \times r}$、$r = o(\log(n))$、$f(x)$は一般的なスカラー関数である。
線形下階近似における以前の研究は、(1)$U = V^\top$と(2)$f(x)$の両方がPSDカーネル関数であれば、$O(nk^{\omega-1})$時間定数相対誤差近似アルゴリズムが存在し、$\omega \approx 2.376$は行列乗算の指数であることを示した。
この問題に対して最初の条件付き時間硬度結果を与え、(1) と (2) の両方の条件が、より広い種類の関数に対する相対誤差低階近似の時間に対して、実際に$n^{2-o(1)} よりも優れていることを示す。
我々は、平坦なスパースベクトルのレバレッジスコアの低界化に依存するStrong Exponential Time hypothesis (SETH) から、変換行列 $f(UV)$ のランクとターゲットランクが $n^{o(1)}$ であり、$U = V^\top$ のランクであっても保持する新しい還元法を提案する。
さらに、$f(x) = x^p$ が単純多項式である場合でも、$U \neq V^\top$ が $\Omega(\min(n^{2-o(1)}, \Omega(2^p)))$ であるような場合、実行時下界を与える。
最後に、我々の下限は、$O(n \cdot \text{poly}(k, 2^p, 1/\epsilon))$時間相対誤差近似アルゴリズムと高速な$O(n \cdot \text{poly}(k, p, 1/\epsilon))$加法誤差近似を高速テンソルベーススケッチを用いて与えることによって、厳密であることを示した。
さらに、我々の低階アルゴリズムは行列ベクトル積のサブルーチンに依存しているため、我々の下限は、小さな行列でさえも$f(UV)W$は$\Omega(n^{2-o(1)})$時間であることを示すために拡張される。
関連論文リスト
- 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) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳（メタデータ） (2023-12-14T12:53:34Z) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - 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) - Fast Attention Requires Bounded Entries [19.17278873525312]
内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。
行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。
このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
論文 参考訳（メタデータ） (2023-02-26T02:42:39Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。