論文の概要: Computing linear sections of varieties: quantum entanglement, tensor
decompositions and beyond
- arxiv url: http://arxiv.org/abs/2212.03851v1
- Date: Wed, 7 Dec 2022 18:45:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-08 17:30:36.860606
- Title: Computing linear sections of varieties: quantum entanglement, tensor
decompositions and beyond
- Title（参考訳）: 多様体の線形切断の計算:量子絡み合い、テンソル分解など
- Authors: Nathaniel Johnston, Benjamin Lovitz and Aravindan Vijayaraghavan
- Abstract要約: 任意の円錐多様体が与えられた線型部分空間と$mathbbFn$の交叉元を求める問題について検討する。
この問題は、多種多様な選択の下で、アルゴリズムの問題の豊富なファミリーを捉えている。
我々は、この問題を「典型的」部分空間に対して解く効率的なアルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 8.604882842499212
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of finding elements in the intersection of an arbitrary
conic variety in $\mathbb{F}^n$ with a given linear subspace (where
$\mathbb{F}$ can be the real or complex field). This problem captures a rich
family of algorithmic problems under different choices of the variety. The
special case of the variety consisting of rank-1 matrices already has strong
connections to central problems in different areas like quantum information
theory and tensor decompositions. This problem is known to be NP-hard in the
worst-case, even for the variety of rank-1 matrices.
Surprisingly, despite these hardness results we give efficient algorithms
that solve this problem for "typical" subspaces. Here, the subspace $U
\subseteq \mathbb{F}^n$ is chosen generically of a certain dimension,
potentially with some generic elements of the variety contained in it. Our main
algorithmic result is a polynomial time algorithm that recovers all the
elements of $U$ that lie in the variety, under some mild non-degeneracy
assumptions on the variety. As corollaries, we obtain the following results:
$\bullet$ Uniqueness results and polynomial time algorithms for generic
instances of a broad class of low-rank decomposition problems that go beyond
tensor decompositions. Here, we recover a decomposition of the form
$\sum_{i=1}^R v_i \otimes w_i$, where the $v_i$ are elements of the given
variety $X$. This implies new algorithmic results even in the special case of
tensor decompositions.
$\bullet$ Polynomial time algorithms for several entangled subspaces problems
in quantum entanglement, including determining $r$-entanglement, complete
entanglement, and genuine entanglement of a subspace. While all of these
problems are NP-hard in the worst case, our algorithm solves them in polynomial
time for generic subspaces of dimension up to a constant multiple of the
maximum possible.
- Abstract（参考訳）: 我々は、与えられた線型部分空間(ここで$\mathbb{F}$は実あるいは複素体)との任意の円錐多様体の交叉における元を見つける問題を研究する。
この問題は、多種多様な選択の下でアルゴリズムの問題の豊富な族を捉えている。
ランク1行列からなる多様体の特殊ケースは、量子情報理論やテンソル分解など、様々な領域における中心問題と強く結びついている。
この問題は、ランク1の様々な行列であっても最悪の場合においてNPハードであることが知られている。
驚くべきことに、これらの困難さにもかかわらず、我々は「典型的な」部分空間でこの問題を解決する効率的なアルゴリズムを与える。
ここで、部分空間 $u \subseteq \mathbb{f}^n$ は、ある次元のジェネリックに選択され、その多様体のいくつかのジェネリック要素がそれに含まれる可能性がある。
我々のアルゴリズムの主な結果は多項式時間アルゴリズムであり、多様体上の穏やかな非退化仮定の下で、多様体に存在する$u$のすべての要素を回復する。
以下の結果が得られる: $\bullet$ uniqueness results and polynomial time algorithms for generic instance of a broad class of low-rank decomposition problems which goes beyond tensor decompositions。
ここでは、$\sum_{i=1}^R v_i \otimes w_i$ という形の分解を復元する。
これはテンソル分解の特別な場合においても新しいアルゴリズムによる結果を意味する。
量子エンタングルメントにおけるいくつかのエンタングル部分空間問題に対する$\bullet$多項式時間アルゴリズムは、$r$エンタングルメント、完全エンタングルメント、真の部分空間のエンタングルメントの決定を含む。
これらの問題はすべて最悪の場合np-hardであるが、本アルゴリズムは最大値の定数倍までの次元の一般部分空間に対して多項式時間で解く。
関連論文リスト
- Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - 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) - A Unifying Framework for Differentially Private Sums under Continual
Observation [20.432568247732206]
本研究では,連続観測下での差分プライベート崩壊和の維持問題について検討する。
十分に滑らかな角関数に対して,この問題に対する統一的枠組みと効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-18T05:04:11Z) - 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) - A Robust Spectral Algorithm for Overcomplete Tensor Decomposition [10.742675209112623]
オーバーコンプリートオーダー4テンソルを分解するスペクトルアルゴリズムを提案する。
我々のアルゴリズムは、有界スペクトルノルムの逆摂動に対して頑健である。
本アルゴリズムは半定値プログラミングを回避し,一連の線形代数演算として実装することができる。
論文 参考訳（メタデータ） (2022-03-05T17:25:37Z) - Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings [9.066817876491053]
我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。
幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。
提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。
我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
論文 参考訳（メタデータ） (2022-02-07T14:43:35Z) - Unique sparse decomposition of low rank matrices [17.037882881652617]
低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。
我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
論文 参考訳（メタデータ） (2021-06-14T20:05:59Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。
他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。
提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文 参考訳（メタデータ） (2021-04-19T17:21:54Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。