論文の概要: An $\ell_p$ theory of PCA and spectral clustering
- arxiv url: http://arxiv.org/abs/2006.14062v3
- Date: Sun, 10 Apr 2022 02:45:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 12:41:24.095322
- Title: An $\ell_p$ theory of PCA and spectral clustering
- Title（参考訳）: PCAとスペクトルクラスタリングの$\ell_p$理論
- Authors: Emmanuel Abbe, Jianqing Fan, Kaizheng Wang
- Abstract要約: 主成分分析は統計と機械学習において強力なツールである。
本稿では、ヒルベルト空間におけるPCAの中空バージョンに対する$ell_p$理論を開発する。
文脈的コミュニティ検出のために、$ell_p$理論は、正確な回復のための情報しきい値を達成する単純なスペクトルアルゴリズムに導かれる。
- 参考スコア（独自算出の注目度）: 23.90245234027558
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Principal Component Analysis (PCA) is a powerful tool in statistics and
machine learning. While existing study of PCA focuses on the recovery of
principal components and their associated eigenvalues, there are few precise
characterizations of individual principal component scores that yield
low-dimensional embedding of samples. That hinders the analysis of various
spectral methods. In this paper, we first develop an $\ell_p$ perturbation
theory for a hollowed version of PCA in Hilbert spaces which provably improves
upon the vanilla PCA in the presence of heteroscedastic noises. Through a novel
$\ell_p$ analysis of eigenvectors, we investigate entrywise behaviors of
principal component score vectors and show that they can be approximated by
linear functionals of the Gram matrix in $\ell_p$ norm, which includes $\ell_2$
and $\ell_\infty$ as special examples. For sub-Gaussian mixture models, the
choice of $p$ giving optimal bounds depends on the signal-to-noise ratio, which
further yields optimality guarantees for spectral clustering. For contextual
community detection, the $\ell_p$ theory leads to a simple spectral algorithm
that achieves the information threshold for exact recovery. These also provide
optimal recovery results for Gaussian mixture and stochastic block models as
special cases.
- Abstract（参考訳）: 主成分分析(PCA)は統計学と機械学習において強力なツールである。
pcaの既存の研究は主成分とその関連する固有値の回復に焦点を当てているが、サンプルの低次元埋め込みをもたらす個々の主成分スコアの正確な特徴はほとんどない。
これは様々なスペクトル法の分析を妨げる。
本稿では, ヒルベルト空間における pca の空洞版に対する $\ell_p$ 摂動理論を最初に考案し, ヘテロシドスティックノイズの存在下でバニラ pca を改良する。
固有ベクトルの新規な$\ell_p$解析により、主成分スコアベクトルのエントリワイズ挙動を調べ、特別な例として$\ell_2$と$\ell_\infty$を含む$\ell_p$ノルムにおけるグラム行列の線形汎関数によって近似できることを示した。
準ガウス混合モデルでは、最適な境界を与える$p$の選択は信号対雑音比に依存し、スペクトルクラスタリングの最適性を保証する。
文脈的コミュニティ検出では、$\ell_p$理論は、正確な回復のための情報しきい値を達成する単純なスペクトルアルゴリズムに繋がる。
また,ガウス混合モデルと確率ブロックモデルに対して,特別な場合として最適回復結果を提供する。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Sparse PCA with Oracle Property [115.72363972222622]
新規な正規化を伴うスパースPCAの半定緩和に基づく推定器群を提案する。
我々は、家族内の別の推定器が、スパースPCAの標準半定緩和よりも、より急激な収束率を達成することを証明した。
論文 参考訳（メタデータ） (2023-12-28T02:52:54Z) - A Tighter Analysis of Spectral Clustering, and Beyond [9.759415650727892]
この研究は、あるグラフ$G=(V_G, E_G)$の頂点を$k$固有ベクトルを使って$mathbbRk$に埋め込む古典的なスペクトルクラスタリングアルゴリズムを研究する。
最初の結果は、スペクトルクラスタリングの性能に関するより厳密な分析であり、なぜそれが文献で研究されているものよりもかなり弱い条件下で機能するのかを説明するものである。
2つ目の結果から、埋め込みを構築するために$k$eigenvectors未満を適用することで、スペクトルクラスタリングが多くの人にとってより良い出力を得られることを示す。
論文 参考訳（メタデータ） (2022-08-02T20:18:07Z) - Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms [9.112172220055431]
一般的な高次元のガウス設計の下で、スパースPCAに対して入出力$ell_2,infty$boundsを提供する。
提案手法は,確率の高い正しいサポートを選択するアルゴリズムであり,スパーシスタントなアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-08T18:50:35Z) - When Random Tensors meet Random Matrices [50.568841545067144]
本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。
検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
論文 参考訳（メタデータ） (2021-12-23T04:05:01Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - 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) - Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale
of Symmetry [9.695960412426672]
我々は,スプリアスミニマの様々な家系でヘッセンを解析的に特徴付ける。
特に、$dge k$ 標準ガウス入力について、 (a) ヘッセンの $dk$ 固有値の内、$dk - O(d)$ が 0 に近づき、 (b) $Omega(d)$ 固有値は $k$ で線型的に増加することを証明している。
論文 参考訳（メタデータ） (2020-08-04T20:08:35Z) - A New Basis for Sparse Principal Component Analysis [5.258928416164104]
以前のスパース主成分分析では、固有基底 ($p 倍 k$ 行列) がほぼスパースであると仮定されていた。
我々は、$p × k$ 行列が、$k × k$ 回転の後にほぼスパースとなると仮定する手法を提案する。
同レベルの疎度では,提案したスパースPCA法の方が安定であり,代替手法よりも分散を説明できることを示す。
論文 参考訳（メタデータ） (2020-07-01T16:32:22Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。
統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。
また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
論文 参考訳（メタデータ） (2020-02-05T00:24:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。