論文の概要: A Gap in the Subrank of Tensors
- arxiv url: http://arxiv.org/abs/2212.01668v1
- Date: Sat, 3 Dec 2022 18:38:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 22:47:45.855742
- Title: A Gap in the Subrank of Tensors
- Title(参考訳): テンソルのサブランクの隙間
- Authors: Matthias Christandl and Fulvio Gesmundo and Jeroen Zuiddam
- Abstract要約: テンソルのサブランクは、テンソルがどれだけ「対角化」できるかの尺度である。
我々は、テンソル積の下で大きなパワーを取るとき、サブランクにギャップがあることを証明した。
また、成長率には第2のギャップがあることも証明しています。
- 参考スコア(独自算出の注目度): 5.253292484834396
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The subrank of tensors is a measure of how much a tensor can be
''diagonalized''. This parameter was introduced by Strassen to study fast
matrix multiplication algorithms in algebraic complexity theory and is closely
related to many central tensor parameters (e.g. slice rank, partition rank,
analytic rank, geometric rank, G-stable rank) and problems in combinatorics,
computer science and quantum information theory. Strassen (J. Reine Angew.
Math., 1988) proved that there is a gap in the subrank when taking large powers
under the tensor product: either the subrank of all powers is at most one, or
it grows as a power of a constant strictly larger than one. In this paper, we
precisely determine this constant for tensors of any order. Additionally, for
tensors of order three, we prove that there is a second gap in the possible
rates of growth. Our results strengthen the recent work of Costa and Dalai (J.
Comb. Theory, Ser. A, 2021), who proved a similar gap for the slice rank. Our
theorem on the subrank has wider applications by implying such gaps not only
for the slice rank, but for any ``normalized monotone''. In order to prove the
main result, we characterize when a tensor has a very structured tensor (the
W-tensor) in its orbit closure. Our methods include degenerations in
Grassmanians, which may be of independent interest.
- Abstract(参考訳): テンソルのサブランク(英: subrank of tensor)とは、テンソルがどれだけ「対角化」できるかの尺度である。
このパラメータは、代数的複雑性理論における高速行列乗法アルゴリズムの研究のためにストラッセンによって導入され、多くの中央テンソルパラメータ(スライスランク、パーティションランク、分析ランク、幾何ランク、G安定ランクなど)と、組合せ論、計算機科学、量子情報理論の問題に密接に関係している。
strassen (j. reine angew. math., 1988) は、テンソル積の下で大きなパワーを取るとき、サブランクにギャップがあることを証明した。
本稿では、任意の順序のテンソルに対するこの定数を正確に決定する。
さらに、次数 3 のテンソルに対して、成長の可能な速度に第二のギャップがあることを証明できる。
我々の結果はコスタとダライの最近の業績(J. Comb. Theory, Ser. A, 2021)を強化し、スライス階の類似のギャップを証明した。
この部分ランク上の定理は、スライスランクだけでなく任意の ``normalized monotone''' に対してもそのようなギャップを暗示することでより広い応用が可能となる。
主な結果を証明するために、テンソルが軌道閉包に非常に構造化されたテンソル(wテンソル)を持つときに特徴付ける。
我々の方法には、独立した関心を持つかもしれない草虫類の退化が含まれる。
関連論文リスト
- Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳(メタデータ) (2024-04-29T14:33:24Z) - Scalable CP Decomposition for Tensor Learning using GPU Tensor Cores [47.87810316745786]
本研究では,エクサスケールテンソル分解を支援する圧縮型テンソル分解フレームワークを提案する。
ベースラインと比較すると、エクスカスケール・テンソルは8000倍のテンソルをサポートし、スピードアップは6.95倍である。
また,本手法を遺伝子解析とテンソル層ニューラルネットワークを含む実世界の2つの応用に適用する。
論文 参考訳(メタデータ) (2023-11-22T21:04:59Z) - The Tensor as an Informational Resource [1.5410557873153832]
テンソル(英: tensor)は、データの保存、計算関係のエンコード、量子絡み合いの表現に使用できる数列である。
テンソル上の情報理論的に構築された事前順序の族を提案し、テンソルを互いに比較し、それらの間の変換の存在を評価する。
論文 参考訳(メタデータ) (2023-11-03T18:47:39Z) - Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
我々は、ある微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。
伊藤鎖の法則と微分方程式の間の$W_2$-距離の有界性を証明する。
論文 参考訳(メタデータ) (2023-10-09T18:38:56Z) - Discreteness of asymptotic tensor ranks [8.202178605741251]
置換ランクとスライスランクは累積点を持たず、複素数に対してスライスランクは累積点を持たないことを示す。
我々のアプローチの中心はテンソルのサブランク上の2つの新しい一般下界であり、テンソルがどれだけ対角化できるかを測定する。
行列部分空間における最大階数に対する新しい下界は、3つの異なる方向に3つのテンソルをスライスすることで得られる。
論文 参考訳(メタデータ) (2023-06-02T17:42:39Z) - Faster Robust Tensor Power Method for Arbitrary Order [15.090593955414137]
emphTensor Power Method (TPM) はテンソルの分解において広く使われている手法の1つである。
我々はスケッチ法を適用し、$widetildeO(np-1)$の出力$p$と dimension$n$tensorで実行時間を達成することができる。
論文 参考訳(メタデータ) (2023-06-01T07:12:00Z) - 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) - Persistent Tensors and Multiqudit Entanglement Transformation [0.07252027234425334]
我々は、持続テンソルの3つの特定の族を示し、そのうちの1つは、下界がきつい。
これら3つの族の間には、それらの間の絡み合いを研究するために使用できる最小ランクの持続テンソルの連鎖が存在することを示す。
論文 参考訳(メタデータ) (2022-11-01T18:00:00Z) - 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) - Dimension of Tensor Network varieties [68.8204255655161]
テンソルネットワーク多様体の次元上の上限を決定する。
洗練された上界は、行列積状態の多様体や射影絡み合ったペア状態のような応用に関係している場合に与えられる。
論文 参考訳(メタデータ) (2021-01-08T18:24:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。