論文の概要: Sparse PCA Beyond Covariance Thresholding
- arxiv url: http://arxiv.org/abs/2302.10158v2
- Date: Wed, 8 Nov 2023 19:15:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-10 18:51:40.273167
- Title: Sparse PCA Beyond Covariance Thresholding
- Title（参考訳）: 分散閾値を超えるスパースPCA
- Authors: Gleb Novikov
- Abstract要約: すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。
スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
- 参考スコア（独自算出の注目度）: 2.311583680973075
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the Wishart model for sparse PCA we are given $n$ samples $Y_1,\ldots,
Y_n$ drawn independently from a $d$-dimensional Gaussian distribution $N({0, Id
+ \beta vv^\top})$, where $\beta > 0$ and $v\in \mathbb{R}^d$ is a $k$-sparse
unit vector, and we wish to recover $v$ (up to sign).
We show that if $n \ge \Omega(d)$, then for every $t \ll k$ there exists an
algorithm running in time $n\cdot d^{O(t)}$ that solves this problem as long as
\[ \beta \gtrsim \frac{k}{\sqrt{nt}}\sqrt{\ln({2 + td/k^2})}\,. \] Prior to
this work, the best polynomial time algorithm in the regime $k\approx
\sqrt{d}$, called \emph{Covariance Thresholding} (proposed in [KNV15a] and
analyzed in [DM14]), required $\beta \gtrsim \frac{k}{\sqrt{n}}\sqrt{\ln({2 +
d/k^2})}$. For large enough constant $t$ our algorithm runs in polynomial time
and has better guarantees than Covariance Thresholding. Previously known
algorithms with such guarantees required quasi-polynomial time $d^{O(\log d)}$.
In addition, we show that our techniques work with sparse PCA with
adversarial perturbations studied in [dKNS20]. This model generalizes not only
sparse PCA, but also other problems studied in prior works, including the
sparse planted vector problem. As a consequence, we provide polynomial time
algorithms for the sparse planted vector problem that have better guarantees
than the state of the art in some regimes.
Our approach also works with the Wigner model for sparse PCA. Moreover, we
show that it is possible to combine our techniques with recent results on
sparse PCA with symmetric heavy-tailed noise [dNNS22]. In particular, in the
regime $k \approx \sqrt{d}$ we get the first polynomial time algorithm that
works with symmetric heavy-tailed noise, while the algorithm from [dNNS22].
requires quasi-polynomial time in these settings.
- Abstract（参考訳）: スパースPCAのウィッシュアートモデルでは、$n$サンプル$Y_1,\ldots, Y_n$を$d$次元ガウス分布$N({0, Id + \beta vv^\top})$から独立に描画し、$\beta > 0$と$v\in \mathbb{R}^d$を$k$スパース単位ベクトルとし、$v$を回復したい。
すると、$n \ge \Omega(d)$ であれば、すべての $t \ll k$ に対して \[ \beta \gtrsim \frac{k}{\sqrt{nt}}\sqrt{\ln({2 + td/k^2})}\ である限り、この問題を解くアルゴリズムが存在することを示す。
この研究に先立ち、$k\approx \sqrt{d}$、すなわち \emph{Covariance Thresholding} ([KNV15a]で提案され、[DM14]で解析された) における最良の多項式時間アルゴリズムは、$\beta \gtrsim \frac{k}{\sqrt{n}}\sqrt{\ln({2 + d/k^2})}$である。
十分大きな定数$t$の場合、我々のアルゴリズムは多項式時間で動き、Covariance Thresholdingよりも保証が高い。
このような保証を持つ既知アルゴリズムは、準多項式時間 $d^{O(\log d)}$ を必要とする。
さらに,本手法は[dKNS20]で研究した対向摂動を伴うスパースPCAで動作することを示す。
このモデルはスパースPCAだけでなく、スパース植込みベクトル問題を含む以前の研究で研究された他の問題も一般化する。
結果として、いくつかのレジームにおける最先端技術よりも優れた保証を持つ疎植ベクトル問題に対する多項式時間アルゴリズムを提供する。
我々のアプローチは、スパースPCAのためのWignerモデルとも連携する。
さらに,本手法とスパースpcaの最近の結果と対称重み付き雑音 [dnns22] を組み合わせることが可能であることを示した。
特に、レジーム $k \approx \sqrt{d}$ では、[dNNS22] のアルゴリズムが対称重み付きノイズを扱う最初の多項式時間アルゴリズムが得られます。
これらの設定では準多項時間を必要とする。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - 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) - Matrix Completion in Almost-Verification Time [37.61139884826181]
99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。
本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
論文 参考訳（メタデータ） (2023-08-07T15:24:49Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。