論文の概要: Approximate tensor decompositions: disappearance of many separations

• arxiv url: http://arxiv.org/abs/2004.10219v2
• Date: Sat, 14 Aug 2021 18:53:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-22 20:29:49.731949
• Title: Approximate tensor decompositions: disappearance of many separations
• Title（参考訳）: 近似テンソル分解:多くの分離の消失
• Authors: Gemma De las Cuevas, Andreas Klingler, Tim Netzer
• Abstract要約: 近似の場合、多くの分離が消えることが示される。 我々の結果は、多くの分離がテンソルの小さな摂動の下では堅牢でないことを示唆している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is well-known that tensor decompositions show separations, that is, that constraints on local terms (such as positivity) may entail an arbitrarily high cost in their representation. Here we show that many of these separations disappear in the approximate case. Specifically, for every approximation error $\varepsilon$ and norm, we define the approximate rank as the minimum rank of an element in the $\varepsilon$-ball with respect to that norm. For positive semidefinite matrices, we show that the separations between rank, purification rank, and separable rank disappear for a large class of Schatten $p$-norms. For nonnegative tensors, we show that the separations between rank, positive semidefinite rank, and nonnegative rank disappear for all $\ell_p$-norms with $p>1$. For the trace norm ($p = 1$), we obtain upper bounds that depend on the ambient dimension. We also provide a deterministic algorithm to obtain the approximate decomposition attaining our bounds. Our main tool is an approximate version of Carath\'eodory's Theorem. Our results imply that many separations are not robust under small perturbations of the tensor, with implications in quantum many-body systems and communication complexity.
• Abstract（参考訳）: テンソル分解は分離、すなわち局所項の制約(肯定性など)がそれらの表現に任意に高いコストを伴っていることを示すことがよく知られている。 ここで、これらの分離の多くは近似の場合消滅することを示す。 具体的には、すべての近似誤差 $\varepsilon$ とノルムに対して、近似ランクを、そのノルムに関して $\varepsilon$-ball の要素の最小ランクとして定義する。 正の半定値行列に対しては、Schatten $p$-norms の大きなクラスに対して階数、浄化階数、分離ランクの分離が消失することを示す。 非負テンソルに対しては、$p>1$のすべての$\ell_p$-ノルムに対してランク、正半定ランク、非負ランクの分離が消えることを示す。 トレースノルム(p = 1$)については、周囲の次元に依存する上界を得る。 また,境界に達する近似分解を求める決定論的アルゴリズムを提案する。 我々の主なツールはカラス・エオドリーの定理の近似版である。 その結果、多くの分離はテンソルの小さな摂動下では頑健ではなく、量子多体系や通信複雑性にも影響することがわかった。

関連論文リスト

• 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)
• Optimal high-precision shadow estimation [22.01044188849049]
  正式には、未知の混合状態$rhoinmathbbCdtimes d$のコピーを$O(log(m)/epsilon2)$に測定するプロトコルを提供します。 次元還元により、$epsilon$と$d$を再スケールして、$epsilon le O(d-1/2)$の政権に還元できることを示す。
  論文  参考訳（メタデータ） (2024-07-18T19:42:49Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates [1.0309387309011746]
  スパースな代替品に対する信号検出問題を、既知のスパシティ$s$に対して検討する。 ミニマックス分離半径$epsilon*$の上の上限と下限を見つけ、それらが常に一致することを証明する。 以上の結果から,epsilon*$の挙動に関する新たな位相遷移が,Sigma$の疎度レベル,$Lt$メトリック,およびヘテロスセダサシティプロファイル(herescedasticity profile)に現れる。
  論文  参考訳（メタデータ） (2022-11-15T23:53:39Z)
• 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)
• Monogamy of entanglement between cones [68.8204255655161]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
  過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。 以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
  論文  参考訳（メタデータ） (2020-10-22T00:32:12Z)
• Extremal elements of a sublattice of the majorization lattice and approximate majorization [0.0]
  一般に、極値確率ベクトルは、閉じた球に対して$mathcalBp_epsilon(x)$に対して1pinfty$で存在しないことを示す。 また、ボールの半径と中心の点から、これらの極端要素を明示的に特徴づける。
  論文  参考訳（メタデータ） (2020-01-23T19:09:18Z)

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

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