論文の概要: Asymptotic tensor rank is characterized by polynomials
- arxiv url: http://arxiv.org/abs/2411.15789v1
- Date: Sun, 24 Nov 2024 11:35:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-26 14:18:20.960913
- Title: Asymptotic tensor rank is characterized by polynomials
- Title（参考訳）: 漸近テンソルランクは多項式によって特徴づけられる
- Authors: Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer, Péter Vrana, Jeroen Zuiddam,
- Abstract要約: ストラッセンの階数予想はテンソル階数がテンソルの最大の次元と等しいという大胆な主張を与える。
我々はランクが "上から計算可能" であることを証明し、すなわち任意の実$r$に対して、$T$のテンソルランクが少なくとも$r$である場合、テンソル$T$を与えられた場合、決定する(効率のよい)アルゴリズムが存在する。
- 参考スコア（独自算出の注目度）: 9.730863921742644
- License:
- Abstract: Asymptotic tensor rank is notoriously difficult to determine. Indeed, determining its value for the $2\times 2$ matrix multiplication tensor would determine the matrix multiplication exponent, a long-standing open problem. On the other hand, Strassen's asymptotic rank conjecture makes the bold claim that asymptotic tensor rank equals the largest dimension of the tensor and is thus as easy to compute as matrix rank. Despite tremendous interest, much is still unknown about the structural and computational properties of asymptotic rank; for instance whether it is computable. We prove that asymptotic tensor rank is "computable from above", that is, for any real number $r$ there is an (efficient) algorithm that determines, given a tensor $T$, if the asymptotic tensor rank of $T$ is at most $r$. The algorithm has a simple structure; it consists of evaluating a finite list of polynomials on the tensor. Indeed, we prove that the sublevel sets of asymptotic rank are Zariski-closed (just like matrix rank). While we do not exhibit these polynomials explicitly, their mere existence has strong implications on the structure of asymptotic rank. As one such implication, we find that the values that asymptotic tensor rank takes, on all tensors, is a well-ordered set. In other words, any non-increasing sequence of asymptotic ranks stabilizes ("discreteness from above"). In particular, for the matrix multiplication exponent (which is an asymptotic rank) there is no sequence of exponents of bilinear maps that approximates it arbitrarily closely from above without being eventually constant. In other words, any upper bound on the matrix multiplication exponent that is close enough, will "snap" to it. Previously such discreteness results were only known for finite fields or for other tensor parameters (e.g., asymptotic slice rank). We obtain them for infinite fields like the complex numbers.
- Abstract（参考訳）: 漸近的なテンソルランクは決定が難しいことで知られている。
実際、2$2\times 2$行列乗算テンソルの値を決定すると、行列乗算指数を決定する。
一方、ストラッセンの漸近的ランク予想(英語版)は、漸近的テンソルランクがテンソルの最大の次元と等しいという大胆な主張をし、したがって行列ランクと同じくらい容易に計算できる。
非常に興味があるにもかかわらず、漸近的ランクの構造的および計算的性質について、例えば計算可能かどうかについては、まだ不明な点が多い。
我々は、漸近テンソルランクが「上から計算可能」であること、すなわち任意の実数$r$に対して、あるテンソル$T$を与えられたとき、その漸近テンソルランクが少なくとも$r$であるならば、(効率のよい)アルゴリズムが存在することを証明する。
アルゴリズムは単純な構造を持ち、テンソル上の多項式の有限リストを評価する。
実際、漸近ランクの下位レベル集合が(行列ランクのように)ザリスキー閉集合であることを証明している。
これらの多項式を明示的に示さないが、それらの単なる存在は漸近階数の構造に強い意味を持つ。
そのような意味合いの1つとして、漸近テンソルランクが取る値は、すべてのテンソル上で、整順序集合であることが分かる。
言い換えれば、漸近的ランクの非増加列は安定化する("discreteness from above")。
特に、行列乗法指数(漸近階数である)に対して、双線型写像の指数列は、最終的に定数となることなく、上から任意に近似する。
言い換えれば、十分近い行列乗法指数上の任意の上界は、それに対して "snap" となる。
以前は、そのような離散性の結果は有限体や他のテンソルパラメータ(例えば漸近スライスランク)に対してのみ知られていた。
複素数のような無限体に対してそれらを得る。
関連論文リスト
- 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) - Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳（メタデータ） (2024-04-29T14:33:24Z) - The Tensor as an Informational Resource [1.3044677039636754]
テンソル(英: tensor)は、データの保存、計算関係のエンコード、量子絡み合いの表現に使用できる数列である。
テンソル上の情報理論的に構築された事前順序の族を提案し、テンソルを互いに比較し、それらの間の変換の存在を評価する。
論文 参考訳（メタデータ） (2023-11-03T18:47:39Z) - On the Accuracy of Hotelling-Type Asymmetric Tensor Deflation: A Random
Tensor Analysis [14.809070996761013]
ホテルリング型テンソルデフレレーションはノイズの存在下で研究されている。
我々は,デフレ手順の各ステップにおいて,推定特異値と推定および真の特異ベクトルのアライメントを解析的に特徴付ける。
論文 参考訳（メタデータ） (2023-10-28T14:40:10Z) - Discreteness of asymptotic tensor ranks [7.916635054977068]
置換ランクとスライスランクは累積点を持たず、複素数に対してスライスランクは累積点を持たないことを示す。
我々のアプローチの中心はテンソルのサブランク上の2つの新しい一般下界であり、テンソルがどれだけ対角化できるかを測定する。
行列部分空間における最大階数に対する新しい下界は、3つの異なる方向に3つのテンソルをスライスすることで得られる。
論文 参考訳（メタデータ） (2023-06-02T17:42:39Z) - A Gap in the Subrank of Tensors [2.7992435001846827]
テンソルのサブランクは、テンソルがどれだけ「対角化」できるかの尺度である。
我々は、テンソル積の下で大きなパワーを取るとき、サブランクにギャップがあることを証明した。
また、成長率には第2のギャップがあることも証明しています。
論文 参考訳（メタデータ） (2022-12-03T18:38:28Z) - 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) - Asymptotic Tensor Powers of Banach Spaces [77.34726150561087]
ユークリッド空間は、そのテンソル半径がその次元と等しい性質によって特徴づけられることを示す。
また、領域または範囲がユークリッドである作用素のテンソル半径がその核ノルムと等しいことを示す。
論文 参考訳（メタデータ） (2021-10-25T11:51:12Z) - Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear
Circuits [4.129484350382891]
深さ$3$の算術回路のクラスに対して、新しい効率的なブラックボックス再構成アルゴリズムを提供する。
我々のアルゴリズムは、すべてのフィールド特性 0 以上の大きな特性に作用する。
論文 参考訳（メタデータ） (2021-05-04T20:45:07Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。