論文の概要: Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor
Decompositions
- arxiv url: http://arxiv.org/abs/2207.07417v3
- Date: Sun, 26 Nov 2023 06:10:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-30 17:41:32.603129
- Title: Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor
Decompositions
- Title（参考訳）: テンソル分解のためのニアリンアー時間と固定パラメータトラクタブルアルゴリズム
- Authors: Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang
- Abstract要約: テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。
テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。
さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
- 参考スコア（独自算出の注目度）: 51.19236668224547
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study low rank approximation of tensors, focusing on the tensor train and
Tucker decompositions, as well as approximations with tree tensor networks and
more general tensor networks. For tensor train decomposition, we give a
bicriteria $(1 + \eps)$-approximation algorithm with a small bicriteria rank
and $O(q \cdot \nnz(A))$ running time, up to lower order terms, which improves
over the additive error algorithm of \cite{huber2017randomized}. We also show
how to convert the algorithm of \cite{huber2017randomized} into a relative
error algorithm, but their algorithm necessarily has a running time of $O(qr^2
\cdot \nnz(A)) + n \cdot \poly(qk/\eps)$ when converted to a $(1 +
\eps)$-approximation algorithm with bicriteria rank $r$. To the best of our
knowledge, our work is the first to achieve polynomial time relative error
approximation for tensor train decomposition. Our key technique is a method for
obtaining subspace embeddings with a number of rows polynomial in $q$ for a
matrix which is the flattening of a tensor train of $q$ tensors. We extend our
algorithm to tree tensor networks. In addition, we extend our algorithm to
tensor networks with arbitrary graphs (which we refer to as general tensor
networks), by using a result of
\cite{ms08_simulating_quantum_tensor_contraction} and showing that a general
tensor network of rank $k$ can be contracted to a binary tree network of rank
$k^{O(\deg(G)\tw(G))}$, allowing us to reduce to the case of tree tensor
networks. Finally, we give new fixed-parameter tractable algorithms for the
tensor train, Tucker, and CP decompositions, which are simpler than those of
\cite{swz19_tensor_low_rank} since they do not make use of polynomial system
solvers. Our technique of Gaussian subspace embeddings with exactly $k$ rows
(and thus exponentially small success probability) may be of independent
interest.
- Abstract（参考訳）: 我々はテンソルの低位近似について研究し、テンソルトレインとタッカー分解、およびツリーテンソルネットワークとより一般的なテンソルネットワークとの近似に焦点を当てた。
テンソルトレインの分解に対して、小さなビクリテリアランクを持つビクリテリア$(1 + \eps)$-approximationアルゴリズムと、低次項までのランニング時間を持つ$O(q \cdot \nnz(A))$を与え、これは \cite{huber2017randomized} の加算誤差アルゴリズムよりも改善する。
huber2017randomized} のアルゴリズムを相対誤差アルゴリズムに変換する方法を示すが、それらのアルゴリズムは、bicriteria ランク $r$ を持つ $(1 + \eps)$近似アルゴリズムに変換するとき、必ず $o(qr^2 \cdot \nnz(a)) + n \cdot \poly(qk/\eps)$ の計算時間を持つ。
我々の知る限り、テンソル列車分解に対する多項式時間相対誤差近似を初めて達成した研究である。
我々の鍵となる手法は、$q$のテンソルのテンソル列の平坦化である行列に対して、$q$の行数多項式を持つ部分空間埋め込みを得る方法である。
我々はアルゴリズムをツリーテンソルネットワークに拡張する。
さらに、このアルゴリズムを任意のグラフを持つテンソルネットワーク(一般テンソルネットワークと呼ぶ)に拡張し、 \cite{ms08_simulating_quantum_tensor_contraction} の結果を用いて、ランク$k$の一般的なテンソルネットワークをランク$k^{O(\deg(G)\tw(G))}$のバイナリツリーネットワークに縮約できることを示し、ツリーテンソルネットワークの場合の削減を可能にした。
最後に、テンソルトレイン、タッカー、cp分解に対して、多項式系解法を使用しないため、より単純である新しい固定パラメータ扱い可能なアルゴリズムを与える。
ちょうど$k$行のガウス部分空間埋め込みの技法(つまり指数関数的に小さい成功確率)は独立な興味を持つ。
関連論文リスト
- Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Fast algorithm for overcomplete order-3 tensor decomposition [7.638467133689933]
我々は、O(d3/2/polylog(d))までのランクRd上のランダムな3階テンソルを分解する最初の高速スペクトルアルゴリズムを開発した。
我々のアルゴリズムは、現在の行列乗算時間の下で全成分を時間O(d6.05)で復元することができる。
論文 参考訳（メタデータ） (2022-02-14T00:31:34Z) - The Complexity of Sparse Tensor PCA [1.90365714903665]
1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。
PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
論文 参考訳（メタデータ） (2021-06-11T10:57:00Z) - Exact nuclear norm, completion and decomposition for random overcomplete
tensors via degree-4 SOS [0.7233897166339269]
次数4$SOSにインスパイアされた単純な半定値プログラムは、ランダムな非対称成分を持つテンソル上のテンソル核ノルム、テンソル分解、テンソル完備化問題を正確に解くことができることを示す。
これらの半定値プログラムは、$(ntimes ntimes n)$-tensor $mathcalT$と$mleq n3/2/polylog(n)$ランダム非対称成分の核ノルムと成分を正確に見つけることができることを示す。
論文 参考訳（メタデータ） (2020-11-18T17:27:36Z) - Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。
以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
論文 参考訳（メタデータ） (2020-10-22T00:32:12Z) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳（メタデータ） (2020-07-09T07:09:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。