論文の概要: Fast algorithm for overcomplete order-3 tensor decomposition

• arxiv url: http://arxiv.org/abs/2202.06442v1
• Date: Mon, 14 Feb 2022 00:31:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-15 18:12:09.445785
• Title: Fast algorithm for overcomplete order-3 tensor decomposition
• Title（参考訳）: オーバーコンプリート3テンソル分解のための高速アルゴリズム
• Authors: Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu, Stefan Tiegel, David Steurer
• Abstract要約: 我々は、O(d3/2/polylog(d))までのランクRd上のランダムな3階テンソルを分解する最初の高速スペクトルアルゴリズムを開発した。 我々のアルゴリズムは、現在の行列乗算時間の下で全成分を時間O(d6.05)で復元することができる。
• 参考スコア（独自算出の注目度）: 7.638467133689933
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop the first fast spectral algorithm to decompose a random third-order tensor over R^d of rank up to O(d^{3/2}/polylog(d)). Our algorithm only involves simple linear algebra operations and can recover all components in time O(d^{6.05}) under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most O(d^{4/3}/polylog(d)). Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm.
• Abstract（参考訳）: o(d^{3/2}/ポリログ(d)) までランクの r^d 上のランダムな三階テンソルを分解する最初の高速スペクトルアルゴリズムを開発した。 我々のアルゴリズムは単純な線形代数演算のみを伴い、現在の行列乗算時間の下ですべての成分を時間 O(d^{6.05}) で復元することができる。 この研究の前には、同等の保証は[ma, shi, steurer 2016]でのみ達成できた。 対照的に、高速アルゴリズム(Hopkins, Schramm, Shi, Steurer 2016)は、ほとんどの O(d^{4/3}/polylog(d)) においてランクテンソルを分解するしかなかった。 アルゴリズムの結果は2つの重要な要素に依存します。 三階テンソルを六階テンソルにクリーンに持ち上げることで、テンソルネットワークの言語で表現できる。 テンソルネットワークを長方行列乗算列に注意深く分解することで、アルゴリズムの高速な実装が可能となる。

関連論文リスト

• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• 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)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• A Robust Spectral Algorithm for Overcomplete Tensor Decomposition [10.742675209112623]
  オーバーコンプリートオーダー4テンソルを分解するスペクトルアルゴリズムを提案する。 我々のアルゴリズムは、有界スペクトルノルムの逆摂動に対して頑健である。 本アルゴリズムは半定値プログラミングを回避し,一連の線形代数演算として実装することができる。
  論文  参考訳（メタデータ） (2022-03-05T17:25:37Z)
• Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits [4.129484350382891]
  深さ$3$の算術回路のクラスに対して、新しい効率的なブラックボックス再構成アルゴリズムを提供する。 我々のアルゴリズムは、すべてのフィールド特性 0 以上の大きな特性に作用する。
  論文  参考訳（メタデータ） (2021-05-04T20:45:07Z)
• Fast Tensor Disentangling Algorithm [0.0]
  本稿では, 互いに絡み合うユニタリテンソルを最適化する近似的, 高速, 簡易なアルゴリズムを提案する。 我々のアルゴリズムは以前の反復アルゴリズムよりも高速であり、しばしば最小の10から40%以内の残絡エントロピーをもたらす。
  論文  参考訳（メタデータ） (2021-04-16T18:00:01Z)
• 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)
• What if Neural Networks had SVDs? [66.91160214071088]
  様々なニューラルネットワークでは、行列反転のような時間を要する行列演算を採用している。 本稿では,行列演算を高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-29T12:58:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。