論文の概要: Low Rank Approximation for General Tensor Networks
- arxiv url: http://arxiv.org/abs/2207.07417v1
- Date: Fri, 15 Jul 2022 11:55:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-18 18:58:22.540828
- Title: Low Rank Approximation for General Tensor Networks
- Title（参考訳）: 一般テンソルネットワークに対する低ランク近似
- Authors: Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang
- Abstract要約: 我々は与えられたテンソルを$q$$Aで近似する問題を研究する。n times ldots times n$ with a arbitrary tensor network of rank $k$ -- すなわち、グラフ$G = (V, E)$。
私たちは、$A$を二分木ネットワーク$T'$と$O(q)$コアで近似し、このネットワークの各エッジの寸法が最大$widetildeO(kO(dt) cdot qとなるようにします。
- 参考スコア（独自算出の注目度）: 55.10347821762229
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of approximating a given tensor with $q$ modes $A \in
\mathbb{R}^{n \times \ldots \times n}$ with an arbitrary tensor network of rank
$k$ -- that is, a graph $G = (V, E)$, where $|V| = q$, together with a
collection of tensors $\{U_v \mid v \in V\}$ which are contracted in the manner
specified by $G$ to obtain a tensor $T$. For each mode of $U_v$ corresponding
to an edge incident to $v$, the dimension is $k$, and we wish to find $U_v$
such that the Frobenius norm distance between $T$ and $A$ is minimized. This
generalizes a number of well-known tensor network decompositions, such as the
Tensor Train, Tensor Ring, Tucker, and PEPS decompositions. We approximate $A$
by a binary tree network $T'$ with $O(q)$ cores, such that the dimension on
each edge of this network is at most $\widetilde{O}(k^{O(dt)} \cdot
q/\varepsilon)$, where $d$ is the maximum degree of $G$ and $t$ is its
treewidth, such that $\|A - T'\|_F^2 \leq (1 + \varepsilon) \|A - T\|_F^2$. The
running time of our algorithm is $O(q \cdot \text{nnz}(A)) + n \cdot
\text{poly}(k^{dt}q/\varepsilon)$, where $\text{nnz}(A)$ is the number of
nonzero entries of $A$. Our algorithm is based on a new dimensionality
reduction technique for tensor decomposition which may be of independent
interest.
We also develop fixed-parameter tractable $(1 + \varepsilon)$-approximation
algorithms for Tensor Train and Tucker decompositions, improving the running
time of Song, Woodruff and Zhong (SODA, 2019) and avoiding the use of generic
polynomial system solvers. We show that our algorithms have a nearly optimal
dependence on $1/\varepsilon$ assuming that there is no $O(1)$-approximation
algorithm for the $2 \to 4$ norm with better running time than brute force.
Finally, we give additional results for Tucker decomposition with robust loss
functions, and fixed-parameter tractable CP decomposition.
- Abstract（参考訳）: 我々は、与えられたテンソルを$q$モードで近似する問題を、$A \in \mathbb{R}^{n \times \ldots \times n}$と、ランク$k$の任意のテンソルネットワーク、すなわちグラフ$G = (V, E)$と、$|V| = q$と、$G$で指定された方法で契約されたテンソル$\{U_v \mid v \in V\}$の集合とで研究する。
エッジインシデントに対応する $u_v$ の各モードに対して、その次元は $k$ であり、$t$ と $a$ の間のフロベニウスノルム距離が最小となるような $u_v$ を求める。
これにより、テンソルトレイン、テンソル環、タッカー、ペップ分解など、多くのよく知られたテンソルネットワーク分解が一般化される。
ここで$d$は最大値が$g$、$t$はそのツリー幅であり、$\|a - t'\|_f^2 \leq (1 + \varepsilon) \|a - t\|_f^2 \leq (1 + \varepsilon) \|a - t\|_f^2$である。
アルゴリズムの実行時間は$O(q \cdot \text{nnz}(A)) + n \cdot \text{poly}(k^{dt}q/\varepsilon)$, ここで$\text{nnz}(A)$は$A$のゼロでないエントリの数である。
このアルゴリズムはテンソル分解のための新しい次元縮小手法に基づいており、これは独立な関心を持つかもしれない。
また、テンソルトレインとタッカー分解のための固定パラメータトラクタブル$(1 + \varepsilon)$-approximationアルゴリズムを開発し、Song, Woodruff and Zhong (SODA, 2019) の実行時間を改善し、汎用多項式システムソルバの使用を避ける。
我々のアルゴリズムは、1/\varepsilon$にほぼ最適依存しており、ブルートフォースよりも動作時間が良い2〜4ドルのノルムに対してo(1)$近似アルゴリズムが存在しないことを仮定している。
最後に,ロバストな損失関数を持つタッカー分解と固定パラメータのcp分解について追加の結果を示す。
関連論文リスト
- 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) - 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) - 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) - Fast algorithm for overcomplete order-3 tensor decomposition [7.638467133689933]
我々は、O(d3/2/polylog(d))までのランクRd上のランダムな3階テンソルを分解する最初の高速スペクトルアルゴリズムを開発した。
我々のアルゴリズムは、現在の行列乗算時間の下で全成分を時間O(d6.05)で復元することができる。
論文 参考訳（メタデータ） (2022-02-14T00:31:34Z) - The Complexity of Sparse Tensor PCA [1.90365714903665]
1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。
PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
論文 参考訳（メタデータ） (2021-06-11T10:57:00Z) - Exact nuclear norm, completion and decomposition for random overcomplete
tensors via degree-4 SOS [0.7233897166339269]
次数4$SOSにインスパイアされた単純な半定値プログラムは、ランダムな非対称成分を持つテンソル上のテンソル核ノルム、テンソル分解、テンソル完備化問題を正確に解くことができることを示す。
これらの半定値プログラムは、$(ntimes ntimes n)$-tensor $mathcalT$と$mleq n3/2/polylog(n)$ランダム非対称成分の核ノルムと成分を正確に見つけることができることを示す。
論文 参考訳（メタデータ） (2020-11-18T17:27:36Z) - Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。
以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
論文 参考訳（メタデータ） (2020-10-22T00:32:12Z) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳（メタデータ） (2020-07-09T07:09:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。