論文の概要: The moment polytope of matrix multiplication is not maximal

• arxiv url: http://arxiv.org/abs/2503.22633v1
• Date: Fri, 28 Mar 2025 17:25:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-31 15:30:50.747545
• Title: The moment polytope of matrix multiplication is not maximal
• Title（参考訳）: 行列乗法におけるモーメントポリトープは極大ではない
• Authors: Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, Jeroen Zuiddam,
• Abstract要約: 行列乗算テンソルのモーメントポリトープと単位テンソルの分離を証明した。 その結果,行列乗法モーメントポリトープは最大値ではないことがわかった。 我々はこれらの手法を拡張し、行列乗法のための最適境界部分ランク境界の新たな証明を得る。
• 参考スコア（独自算出の注目度）: 3.1593341358400737
• License:
• Abstract: Moment polytopes of tensors, the study of which is deeply rooted in invariant theory, representation theory and symplectic geometry, have found relevance in numerous places, from quantum information (entanglement polytopes) and algebraic complexity theory (GCT program and the complexity of matrix multiplication) to optimization (scaling algorithms). Towards an open problem in algebraic complexity theory, we prove separations between the moment polytopes of matrix multiplication tensors and unit tensors. As a consequence, we find that matrix multiplication moment polytopes are not maximal, i.e. are strictly contained in the corresponding Kronecker polytope. As another consequence, we obtain a no-go result for a natural operational characterization of moment polytope inclusion in terms of asymptotic restriction. We generalize the separation and non-maximality to moment polytopes of iterated matrix multiplication tensors. Our result implies that tensor networks where multipartite entanglement structures beyond two-party entanglement are allowed can go beyond projected entangled-pair states (PEPS) in terms of expressivity. Our proof characterizes membership of uniform points in moment polytopes of tensors, and establishes a connection to polynomial multiplication tensors via the minrank of matrix subspaces. As a result of independent interest, we extend these techniques to obtain a new proof of the optimal border subrank bound for matrix multiplication.
• Abstract（参考訳）: テンソルのモーメント・ポリトープは不変理論、表現理論、シンプレクティック幾何学に深く根付いており、量子情報(絡み合ったポリトープ)や代数的複雑性理論(GCTプログラム、行列乗算の複雑さ)から最適化(スケーリングアルゴリズム)まで、多くの場所で関係している。 代数的複雑性理論の開問題に向けて、行列乗算テンソルのモーメントポリトープと単位テンソルの分離を証明した。 その結果、行列乗法モーメントポリトープは極大ではなく、すなわち対応するクロネッカーポリトープに厳密に含まれていることが判明した。 もう一つの結果として、漸近的制約の観点から、モーメント・ポリトープの自然な操作的特徴付けにノーゴー結果が得られる。 我々は、反復行列乗算テンソルのモーメントポリトープへの分離と非最大性を一般化する。 この結果から,多部交絡構造が両端交絡構造を越えて許されるテンソルネットワークは,表現性の観点からは射影交絡対状態(PEPS)を超えることが可能であることが示唆された。 我々の証明はテンソルのモーメントポリトープにおける一様点のメンバシップを特徴づけ、行列部分空間の最小化による多項式乗法テンソルへの接続を確立する。 独立な関心の結果、これらの手法を拡張して、行列乗法のための最適境界部分ランク境界の新たな証明を得る。

関連論文リスト

• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。 重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。 我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
  論文  参考訳（メタデータ） (2024-05-23T12:26:25Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• The polygon relation and subadditivity of entropic measures for discrete and continuous multipartite entanglement [0.6759148939470331]
  エントロピーの多角形関係と部分付加率の関係について検討した。 我々の研究は多粒子状態の豊富な構造をよりよく理解する。
  論文  参考訳（メタデータ） (2024-01-04T05:09:37Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Polynomial decompositions with invariance and positivity inspired by tensors [1.433758865948252]
  このフレームワークは、特に量子多体系において、テンソル分解のために最近導入された。 我々は、構造、近似、実数に対する決定不可能性の不変分解を定義する。 私たちの仕事は、足場をテンソルで均等な足場に置き、このフレームワークを他の製品構造に拡張する扉を開くことで、足場に新たな光を当てます。
  論文  参考訳（メタデータ） (2021-09-14T13:30:50Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• Positive maps and trace polynomials from the symmetric group [0.0]
  いくつかの変数の演算子不等式と同一性を求める手法を開発した。 量子情報理論と不変理論の概念に関連性を与える。
  論文  参考訳（メタデータ） (2020-02-28T17:43:37Z)
• Matrix product operator representation of polynomial interactions [0.0]
  格子サイト分離を行列積演算子(MPO)として指数関数として成長する1次元格子上の相互作用ハミルトニアンの正確な構成を提供する。 本研究は,多体量子演算子の相関構造に関する新たな知見を提供するとともに,対話を指数的に探索する多体系のシミュレーションにも有効である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-01-14T04:15:32Z)

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

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