論文の概要: Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS

• arxiv url: http://arxiv.org/abs/2011.09416v2
• Date: Thu, 28 Oct 2021 17:59:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-24 03:54:56.345463
• Title: Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
• Title（参考訳）: 次数4SOSによるランダムオーバーコンプリートテンソルの核ノルム、完備化と分解
• Authors: Bohdan Kivva and Aaron Potechin
• Abstract要約: 次数4$SOSにインスパイアされた単純な半定値プログラムは、ランダムな非対称成分を持つテンソル上のテンソル核ノルム、テンソル分解、テンソル完備化問題を正確に解くことができることを示す。 これらの半定値プログラムは、$(ntimes ntimes n)$-tensor $mathcalT$と$mleq n3/2/polylog(n)$ランダム非対称成分の核ノルムと成分を正確に見つけることができることを示す。
• 参考スコア（独自算出の注目度）: 0.7233897166339269
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we show that simple semidefinite programs inspired by degree $4$ SOS can exactly solve the tensor nuclear norm, tensor decomposition, and tensor completion problems on tensors with random asymmetric components. More precisely, for tensor nuclear norm and tensor decomposition, we show that w.h.p. these semidefinite programs can exactly find the nuclear norm and components of an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m\leq n^{3/2}/polylog(n)$ random asymmetric components. Unlike most of the previous algorithms, our algorithm provides a certificate for the decomposition, does not require knowledge about the number of components in the decomposition and does not make any assumptions on the sizes of the coefficients in the decomposition. As a byproduct, we show that w.h.p. the nuclear norm decomposition exactly coincides with the minimum rank decomposition for tensors with $m\leq n^{3/2}/polylog(n)$ random asymmetric components. For tensor completion, we show that w.h.p. the semidefinite program, introduced by Potechin & Steurer (2017) for tensors with orthogonal components, can exactly recover an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m$ random asymmetric components from only $n^{3/2}m polylog(n)$ randomly observed entries. For non-orthogonal tensors, this improves the dependence on $m$ of the number of entries needed for exact recovery over all previously known algorithms and provides the first theoretical guarantees for exact tensor completion in the overcomplete regime.
• Abstract（参考訳）: 本稿では、次数4$SOSにインスパイアされた単純な半定値プログラムは、ランダムな非対称成分を持つテンソル上のテンソル核ノルム、テンソル分解、テンソル完備化問題を正確に解くことができることを示す。 より正確には、テンソル核ノルムとテンソル分解について、w.h.p. の半定義プログラムは、正確には $(n\times n\times n)$-tensor $\mathcal{t}$ with $m\leq n^{3/2}/polylog(n)$ の非対称成分の核ノルムと成分を見つけることができる。 従来のアルゴリズムとは異なり、我々のアルゴリズムは分解の証明を提供しており、分解における成分の数に関する知識は必要とせず、分解における係数のサイズに関する仮定も必要としない。 副生成物として、核ノルム分解は、$m\leq n^{3/2}/polylog(n)$ランダム非対称成分を持つテンソルの最小階分解と正確に一致することを示す。 テンソルの完全性については、potechin & steurer (2017) が直交成分を持つテンソルに対して導入した半定義プログラム w.h.p. が、$(n\times n\times n)$-tensor $\mathcal{t}$ を、わずか$n^{3/2}m polylog(n)$ からランダムな非対称成分で正確に回収できることを示す。 非直交テンソルに対しては、既知の全てのアルゴリズムに対して正確な回復に必要なエントリ数の$m$への依存を改善し、オーバーコンプリートにおける正確なテンソル完備に対する最初の理論的保証を提供する。

関連論文リスト

• On the Accuracy of Hotelling-Type Asymmetric Tensor Deflation: A Random Tensor Analysis [14.809070996761013]
  ホテルリング型テンソルデフレレーションはノイズの存在下で研究されている。 我々は,デフレ手順の各ステップにおいて,推定特異値と推定および真の特異ベクトルのアライメントを解析的に特徴付ける。
  論文  参考訳（メタデータ） (2023-10-28T14:40:10Z)
• On the Accuracy of Hotelling-Type Tensor Deflation: A Random Tensor Analysis [16.28927188636617]
  階数-$r$ の $sum_i=1r beta_i A_i + W$ の非対称スパイクモデルを考える。 本研究では, ホテルリング型デフレに関する研究を行った。
  論文  参考訳（メタデータ） (2022-11-16T16:01:56Z)
• 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)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• A Robust Spectral Algorithm for Overcomplete Tensor Decomposition [10.742675209112623]
  オーバーコンプリートオーダー4テンソルを分解するスペクトルアルゴリズムを提案する。 我々のアルゴリズムは、有界スペクトルノルムの逆摂動に対して頑健である。 本アルゴリズムは半定値プログラミングを回避し,一連の線形代数演算として実装することができる。
  論文  参考訳（メタデータ） (2022-03-05T17:25:37Z)
• When Random Tensors meet Random Matrices [50.568841545067144]
  本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。 検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
  論文  参考訳（メタデータ） (2021-12-23T04:05:01Z)
• Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
  過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。 以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
  論文  参考訳（メタデータ） (2020-10-22T00:32:12Z)

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

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