論文の概要: Discreteness of asymptotic tensor ranks

• arxiv url: http://arxiv.org/abs/2306.01718v2
• Date: Fri, 22 Sep 2023 15:32:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-25 18:44:44.688604
• Title: Discreteness of asymptotic tensor ranks
• Title（参考訳）: 漸近テンソルランクの離散性
• Authors: Jop Bri\"et, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam
• Abstract要約: 置換ランクとスライスランクは累積点を持たず、複素数に対してスライスランクは累積点を持たないことを示す。 我々のアプローチの中心はテンソルのサブランク上の2つの新しい一般下界であり、テンソルがどれだけ対角化できるかを測定する。 行列部分空間における最大階数に対する新しい下界は、3つの異なる方向に3つのテンソルをスライスすることで得られる。
• 参考スコア（独自算出の注目度）: 8.202178605741251
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tensor parameters that are amortized or regularized over large tensor powers, often called "asymptotic" tensor parameters, play a central role in several areas including algebraic complexity theory (constructing fast matrix multiplication algorithms), quantum information (entanglement cost and distillable entanglement), and additive combinatorics (bounds on cap sets, sunflower-free sets, etc.). Examples are the asymptotic tensor rank, asymptotic slice rank and asymptotic subrank. Recent works (Costa-Dalai, Blatter-Draisma-Rupniewski, Christandl-Gesmundo-Zuiddam) have investigated notions of discreteness (no accumulation points) or "gaps" in the values of such tensor parameters. We prove a general discreteness theorem for asymptotic tensor parameters of order-three tensors and use this to prove that (1) over any finite field (and in fact any finite set of coefficients in any field), the asymptotic subrank and the asymptotic slice rank have no accumulation points, and (2) over the complex numbers, the asymptotic slice rank has no accumulation points. Central to our approach are two new general lower bounds on the asymptotic subrank of tensors, which measures how much a tensor can be diagonalized. The first lower bound says that the asymptotic subrank of any concise three-tensor is at least the cube-root of the smallest dimension. The second lower bound says that any concise three-tensor that is "narrow enough" (has one dimension much smaller than the other two) has maximal asymptotic subrank. Our proofs rely on new lower bounds on the maximum rank in matrix subspaces that are obtained by slicing a three-tensor in the three different directions. We prove that for any concise tensor, the product of any two such maximum ranks must be large, and as a consequence there are always two distinct directions with large max-rank.
• Abstract（参考訳）: テンソルのパラメータは、しばしば「漸近的」テンソルパラメータと呼ばれ、代数的複雑性理論(高速な行列乗算アルゴリズムを構築する)、量子情報(絡み合いコストと蒸留可能な絡み合い)、加法組合せ(キャップセット上の束縛、ひまわりなし集合など)など、いくつかの分野において中心的な役割を果たす。 例えば、漸近テンソルランク、漸近スライスランク、漸近サブランクなどである。 最近の研究 (Costa-Dalai, Blatter-Draisma-Rupniewski, Christandl-Gesmundo-Zuiddam) では、そのようなテンソルパラメータの値における離散性(累積点を持たない)や「ギャップ」の概念が研究されている。 我々は、次数3テンソルの漸近テンソルパラメータに対する一般離散性定理を証明し、(1)任意の有限体上の(そして実際に任意の体における任意の有限個の係数の集合)漸近部分ランクと漸近スライスランクが蓄積点を持たず、(2)複素数上、漸近スライスランクは蓄積点を持たないことを証明するためにこれを用いる。 我々のアプローチの中心はテンソルの漸近部分ランクの2つの新しい一般下界であり、テンソルがどれだけ対角化できるかを測定する。 最初の下限は、簡潔な3つのテンソルの漸近部分ランクが少なくとも最小次元の立方根であることを示している。 2つ目の下限は、(他の2よりはるかに小さい1次元を持つ)「十分小さい」簡潔な3つのテンソルは極大漸近部分ランクを持つことを示している。 我々の証明は、行列部分空間の最大階数に対する新しい下界に依存し、3つの異なる方向に3つのテンソルをスライスすることで得られる。 任意の簡潔テンソルに対して、そのような2つの最大ランクの積は大きいものでなければならず、その結果、常に2つの異なる方向があり、最大ランクが大きいことが証明される。

関連論文リスト

• Asymptotic tensor rank is characterized by polynomials [9.730863921742644]
  ストラッセンの階数予想はテンソル階数がテンソルの最大の次元と等しいという大胆な主張を与える。 我々はランクが "上から計算可能" であることを証明し、すなわち任意の実$r$に対して、$T$のテンソルランクが少なくとも$r$である場合、テンソル$T$を与えられた場合、決定する(効率のよい)アルゴリズムが存在する。
  論文  参考訳（メタデータ） (2024-11-24T11:35:38Z)
• 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 next gap in the subrank of 3-tensors [3.8073142980733]
  我々は、任意の零でない3つのテンソルのランクとスライスランクが離散的であることを示す(いくつかのレジームにおいて)。 次のギャップを正確に決定し、任意の 0 でない 3 個のテンソルのランクとスライスランクが離散的であることを示す(いくつかのレギュレーションにおいて)。
  論文  参考訳（メタデータ） (2023-07-12T12:14:54Z)
• 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)
• Persistent Tensors and Multiqudit Entanglement Transformation [0.07252027234425334]
  我々は、持続テンソルの3つの特定の族を示し、そのうちの1つは、下界がきつい。 これら3つの族の間には、それらの間の絡み合いを研究するために使用できる最小ランクの持続テンソルの連鎖が存在することを示す。
  論文  参考訳（メタデータ） (2022-11-01T18:00:00Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Dimension of Tensor Network varieties [68.8204255655161]
  テンソルネットワーク多様体の次元上の上限を決定する。 洗練された上界は、行列積状態の多様体や射影絡み合ったペア状態のような応用に関係している場合に与えられる。
  論文  参考訳（メタデータ） (2021-01-08T18:24:50Z)
• 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)

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

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