論文の概要: Thresholded Oja does Sparse PCA?
- arxiv url: http://arxiv.org/abs/2402.07240v2
- Date: Tue, 20 Feb 2024 05:43:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-22 18:46:49.167006
- Title: Thresholded Oja does Sparse PCA?
- Title(参考訳): 閾値オジャはpcaを弱めるか?
- Authors: Syamantak Kumar and Purnamrita Sarkar
- Abstract要約: Ojaのアルゴリズムの出力をしきい値にし、再正規化する単純なアルゴリズムが、ほぼ最適誤差率を得ることを示す。
解析は、非正規化 Oja ベクトルの成分の有界化を中心に行われる。
- 参考スコア(独自算出の注目度): 8.339831319589134
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of Sparse Principal Component Analysis (PCA) when the
ratio $d/n \rightarrow c > 0$. There has been a lot of work on optimal rates on
sparse PCA in the offline setting, where all the data is available for multiple
passes. In contrast, when the population eigenvector is $s$-sparse, streaming
algorithms that have $O(d)$ storage and $O(nd)$ time complexity either
typically require strong initialization conditions or have a suboptimal error.
We show that a simple algorithm that thresholds and renormalizes the output of
Oja's algorithm (the Oja vector) obtains a near-optimal error rate. This is
very surprising because, without thresholding, the Oja vector has a large
error. Our analysis centers around bounding the entries of the unnormalized Oja
vector, which involves the projection of a product of independent random
matrices on a random initial vector. This is nontrivial and novel since
previous analyses of Oja's algorithm and matrix products have been done when
the trace of the population covariance matrix is bounded while in our setting,
this quantity can be as large as $n$.
- Abstract(参考訳): スパース主成分分析(PCA)の問題は、$d/n \rightarrow c > 0$である。
オフライン環境では、すべてのデータが複数のパスで利用できる、スパースPCAの最適レートについて多くの研究がなされている。
対照的に、人口固有ベクトルが$s$-sparseである場合、ストリーミングアルゴリズムは$o(d)$ストレージと$o(nd)$時間の複雑さを持つ。
我々はOjaのアルゴリズム(Ojaベクトル)の出力をしきい値と再正規化する単純なアルゴリズムが、ほぼ最適誤差率を得ることを示す。
しきい値がなければ、Ojaベクトルは大きな誤差を持つため、これは非常に驚くべきことである。
解析は、ランダム初期ベクトル上の独立なランダム行列の積の射影を含む非正規化 oja ベクトルのエントリを束縛することに集中する。
このことは、Ojaのアルゴリズムと行列積の以前の解析は、我々の設定において、集団共分散行列のトレースが有界であるときに行われており、この量は$n$にも達する。
関連論文リスト
- Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳(メタデータ) (2023-06-07T14:07:35Z) - Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。
スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文 参考訳(メタデータ) (2023-02-20T18:45:24Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [48.07596965953344]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に,m = (klog(n))O(t)/alpha と m = (klog(n))O(t)/alpha と、m = (mnt)$ と、m = (klog(n))O(t)/alpha と、m = (1/alpha)O (1/t)$ の誤差を達成する。
論文 参考訳(メタデータ) (2022-06-10T17:38:18Z) - Improved analysis of randomized SVD for top-eigenvector approximation [16.905540623795467]
そこで本研究では,無作為なSVDアルゴリズムであるcitethalko2011finding を新たに解析し,興味のある場合の厳密な境界を導出する。
特に、これは任意の反復数を持つランダム化SVDに対して$R(hatmathbfu)$の非自明な境界を与える最初の作品である。
論文 参考訳(メタデータ) (2022-02-16T11:12:07Z) - Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected
Error [0.3997680012976965]
目標は、最悪の予測エラーを最小限に抑える推定器を設計することである。
Chen, Valiant および Valiant は、データ値が $ell_infty$-normalized の場合、平均の推定値を計算する時間アルゴリズムが存在することを示した。
本稿では,オンライン凸最適化に基づく最適半線形推定器の近似アルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-12-27T18:47:25Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond
rank-one updates [14.728207711693406]
Ojaの$k$-PCAストリーミングアルゴリズムは、最適なオフラインアルゴリズムとほぼ一致する性能を達成する。
我々はOjaのアルゴリズムが期待値のトップ$k$固有ベクトルの部分空間への正確な近似を得ることができることを示す。
論文 参考訳(メタデータ) (2021-02-06T19:21:24Z) - 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) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳(メタデータ) (2020-10-19T16:45:37Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-09-30T19:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。