論文の概要: Overcomplete Tensor Decomposition via Koszul-Young Flattenings

• arxiv url: http://arxiv.org/abs/2411.14344v1
• Date: Thu, 21 Nov 2024 17:41:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-22 15:17:56.003187
• Title: Overcomplete Tensor Decomposition via Koszul-Young Flattenings
• Title（参考訳）: Koszul-Young Flatteningによる超完全テンソル分解
• Authors: Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein,
• Abstract要約: 最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。 次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
• 参考スコア（独自算出の注目度）: 63.01248796170617
• License:
• Abstract: Motivated by connections between algebraic complexity lower bounds and tensor decompositions, we investigate Koszul-Young flattenings, which are the main ingredient in recent lower bounds for matrix multiplication. Based on this tool we give a new algorithm for decomposing an $n_1 \times n_2 \times n_3$ tensor as the sum of a minimal number of rank-1 terms, and certifying uniqueness of this decomposition. For $n_1 \le n_2 \le n_3$ with $n_1 \to \infty$ and $n_3/n_2 = O(1)$, our algorithm is guaranteed to succeed when the tensor rank is bounded by $r \le (1-\epsilon)(n_2 + n_3)$ for an arbitrary $\epsilon > 0$, provided the tensor components are generically chosen. For any fixed $\epsilon$, the runtime is polynomial in $n_3$. When $n_2 = n_3 = n$, our condition on the rank gives a factor-of-2 improvement over the classical simultaneous diagonalization algorithm, which requires $r \le n$, and also improves on the recent algorithm of Koiran (2024) which requires $r \le 4n/3$. It also improves on the PhD thesis of Persu (2018) which solves rank detection for $r \leq 3n/2$. We complement our upper bounds by showing limitations, in particular that no flattening of the style we consider can surpass rank $n_2 + n_3$. Furthermore, for $n \times n \times n$ tensors, we show that an even more general class of degree-$d$ polynomial flattenings cannot surpass rank $Cn$ for a constant $C = C(d)$. This suggests that for tensor decompositions, the case of generic components may be fundamentally harder than that of random components, where efficient decomposition is possible even in highly overcomplete settings.
• Abstract（参考訳）: 代数的複雑性の下界とテンソル分解の接続により動機付け、近年の行列乗法において主要な要素であるKoszul-Young平坦化について検討する。 このツールに基づいて、最小ランク1項の和として$n_1 \times n_2 \times n_3$ tensorを分解し、この分解の特異性を証明するための新しいアルゴリズムを与える。 このアルゴリズムは、$n_1 \le n_2 \le n_3$ with $n_1 \to \infty$ and $n_3/n_2 = O(1)$に対して、テンソル階数が$r \le (1-\epsilon)(n_2 + n_3)$ for an arbitrary $\epsilon > 0$ で有界であるときに成功することが保証される。 任意の固定$\epsilon$に対して、ランタイムは$n_3$の多項式である。 n2 = n_3 = n$のとき、このランクの条件は、$r \le n$を必要とする古典的同時対角化アルゴリズムよりも2倍改善され、また、$r \le 4n/3$を必要とする最近のKoiran (2024)のアルゴリズムも改善される。 また、$r \leq 3n/2$のランク検出を解くPersu (2018) の博士論文も改善されている。 特に、我々が考慮しているスタイルの平坦化が階数$n_2 + n_3$を超えないことを示して、上界を補完する。 さらに、$n \times n \times n$ tensors に対して、次数-$d$多項式平坦化のより一般的なクラスが定数 $C = C(d)$ に対して階数 $Cn$ を超えないことが示される。 これは、テンソル分解の場合、ジェネリック成分のケースは、高度にオーバーコンプリートされた設定でも効率的な分解が可能で、ランダム成分のケースよりも根本的に難しいかもしれないことを示唆している。

関連論文リスト

• How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation [12.853829771559916]
  本稿では,三重相関を捉える注意の一般化について検討する。 この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。 構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
  論文  参考訳（メタデータ） (2023-10-06T07:42:39Z)
• 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)
• Solving Tensor Low Cycle Rank Approximation [15.090593955414137]
  特定のテンソル低ランク近似問題を定式化し、テンソルサイクルランク(tensor cycle rank)と呼ぶことができる。 テンソルの古典的位階、タッカーの位階、列車の位階については、[Song, Woodruff, Soda Zhong 2019]でよく研究されている。 本稿では, [Song, Woodruff, Zhong SODA 2019] のページで, 以前の回転とスケッチのテクニックを一般化し, サイクルランクの入力空間時間アルゴリズムを示す。
  論文  参考訳（メタデータ） (2023-04-13T15:00:50Z)
• 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)
• Monogamy of entanglement between cones [68.8204255655161]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• 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)

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

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