論文の概要: The Complexity of Sparse Tensor PCA
- arxiv url: http://arxiv.org/abs/2106.06308v1
- Date: Fri, 11 Jun 2021 10:57:00 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-14 14:20:02.243811
- Title: The Complexity of Sparse Tensor PCA
- Title（参考訳）: スパーステンソルPCAの複雑さ
- Authors: Davin Choo, Tommaso d'Orsi
- Abstract要約: 1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。
PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
- 参考スコア（独自算出の注目度）: 1.90365714903665
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of sparse tensor principal component analysis: given a
tensor $\pmb Y = \pmb W + \lambda x^{\otimes p}$ with $\pmb W \in
\otimes^p\mathbb{R}^n$ having i.i.d. Gaussian entries, the goal is to recover
the $k$-sparse unit vector $x \in \mathbb{R}^n$. The model captures both sparse
PCA (in its Wigner form) and tensor PCA.
For the highly sparse regime of $k \leq \sqrt{n}$, we present a family of
algorithms that smoothly interpolates between a simple polynomial-time
algorithm and the exponential-time exhaustive search algorithm. For any $1 \leq
t \leq k$, our algorithms recovers the sparse vector for signal-to-noise ratio
$\lambda \geq \tilde{\mathcal{O}} (\sqrt{t} \cdot (k/t)^{p/2})$ in time
$\tilde{\mathcal{O}}(n^{p+t})$, capturing the state-of-the-art guarantees for
the matrix settings (in both the polynomial-time and sub-exponential time
regimes).
Our results naturally extend to the case of $r$ distinct $k$-sparse signals
with disjoint supports, with guarantees that are independent of the number of
spikes. Even in the restricted case of sparse PCA, known algorithms only
recover the sparse vectors for $\lambda \geq \tilde{\mathcal{O}}(k \cdot r)$
while our algorithms require $\lambda \geq \tilde{\mathcal{O}}(k)$.
Finally, by analyzing the low-degree likelihood ratio, we complement these
algorithmic results with rigorous evidence illustrating the trade-offs between
signal-to-noise ratio and running time. This lower bound captures the known
lower bounds for both sparse PCA and tensor PCA. In this general model, we
observe a more intricate three-way trade-off between the number of samples $n$,
the sparsity $k$, and the tensor power $p$.
- Abstract（参考訳）: a tensor $\pmb Y = \pmb W + \lambda x^{\otimes p}$ with $\pmb W \in \otimes^p\mathbb{R}^n$ having i.d。
gaussianエントリ 目標は、$k$-sparse 単位ベクトル $x \in \mathbb{r}^n$を回復することである。
このモデルはスパースPCA(ウィグナー形式)とテンソルPCAの両方をキャプチャする。
k \leq \sqrt{n}$ の非常にスパースな状態に対して、単純な多項式時間アルゴリズムと指数時間排他的探索アルゴリズムをスムーズに補間するアルゴリズムの族を示す。
任意の 1 ドルの \leq t \leq k$ に対して、我々のアルゴリズムは信号対雑音比 $\lambda \geq \tilde{\mathcal{o}} (\sqrt{t} \cdot (k/t)^{p/2})$ in time $\tilde{\mathcal{o}}(n^{p+t})$ のスパースベクトルを復元し、行列の設定(多項式時間とサブ指数時間)の保証をキャプチャする。
我々の結果は当然、$r$ distinct $k$-sparse signal with disjoint support, which is independent of the number of spikes。
スパースPCAの制限された場合においても、既知のアルゴリズムは、$\lambda \geq \tilde{\mathcal{O}}(k \cdot r)$に対してのみスパースベクトルを復元するが、我々のアルゴリズムは$\lambda \geq \tilde{\mathcal{O}}(k)$を必要とする。
最後に,低次度比を解析することにより,信号対雑音比と走行時間とのトレードオフを示す厳密な証拠を用いて,これらのアルゴリズム結果を補完する。
この下界は、スパースPCAとテンソルPCAの両方の既知の下界をキャプチャする。
この一般的なモデルでは、サンプル数$n$、スパーシティ$k$、テンソルパワー$p$の間のより複雑な3方向のトレードオフを観察します。
関連論文リスト
- 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) - A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文 参考訳（メタデータ） (2024-03-07T18:23:51Z) - Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。
Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
論文 参考訳（メタデータ） (2024-02-11T16:36:48Z) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳（メタデータ） (2023-12-14T12:53:34Z) - 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) - Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。
スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文 参考訳（メタデータ） (2023-02-20T18:45:24Z) - 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) - 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) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。