論文の概要: Subspace clustering in high-dimensions: Phase transitions \&
Statistical-to-Computational gap
- arxiv url: http://arxiv.org/abs/2205.13527v1
- Date: Thu, 26 May 2022 17:47:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-27 13:49:40.535633
- Title: Subspace clustering in high-dimensions: Phase transitions \&
Statistical-to-Computational gap
- Title（参考訳）: 高次元空間におけるサブスペースクラスタリング:相転移 \&統計的-計算的ギャップ
- Authors: Luca Pesce, Bruno Loureiro, Florent Krzakala, Lenka Zdeborov\'a
- Abstract要約: 部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。
広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
- 参考スコア（独自算出の注目度）: 24.073221004661427
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A simple model to study subspace clustering is the high-dimensional
$k$-Gaussian mixture model where the cluster means are sparse vectors. Here we
provide an exact asymptotic characterization of the statistically optimal
reconstruction error in this model in the high-dimensional regime with
extensive sparsity, i.e. when the fraction of non-zero components of the
cluster means $\rho$, as well as the ratio $\alpha$ between the number of
samples and the dimension are fixed, while the dimension diverges. We identify
the information-theoretic threshold below which obtaining a positive
correlation with the true cluster means is statistically impossible.
Additionally, we investigate the performance of the approximate message passing
(AMP) algorithm analyzed via its state evolution, which is conjectured to be
optimal among polynomial algorithm for this task. We identify in particular the
existence of a statistical-to-computational gap between the algorithm that
require a signal-to-noise ratio $\lambda_{\text{alg}} \ge k / \sqrt{\alpha} $
to perform better than random, and the information theoretic threshold at
$\lambda_{\text{it}} \approx \sqrt{-k \rho \log{\rho}} / \sqrt{\alpha}$.
Finally, we discuss the case of sub-extensive sparsity $\rho$ by comparing the
performance of the AMP with other sparsity-enhancing algorithms, such as
sparse-PCA and diagonal thresholding.
- Abstract（参考訳）: 部分空間クラスタリングを研究するための単純なモデルは、クラスタ平均がスパースベクトルである高次元の$k$-gaussian混合モデルである。
ここでは,非零成分の割合が$\rho$ である場合や,サンプル数と次元との比 $\alpha$ が固定されている場合,次元が分岐する高次元領域において,このモデルにおける統計的に最適な再構成誤差の正確な漸近的特性を示す。
我々は、真クラスタ平均との正の相関が統計的に不可能な情報理論しきい値を特定する。
さらに,その状態進化を通じて解析された近似メッセージパッシング(amp)アルゴリズムの性能について検討した。
特に、信号対雑音比$\lambda_{\text{alg}} \ge k / \sqrt{\alpha} $ を必要とするアルゴリズムと$\lambda_{\text{it}} \approx \sqrt{-k \rho \log{\rho}} / \sqrt{\alpha}$ における情報理論上のしきい値との間の統計的-計算間ギャップの存在を同定する。
最後に、AMPの性能をスパースPCAや対角しきい値設定などの他の疎度向上アルゴリズムと比較することにより、サブエクスポーシティ$\rho$の場合について論じる。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Heteroskedastic Tensor Clustering [20.979358557219953]
我々は、$mathsfHightext-orderHeteroClustering$$mathsfHHC$という2段階の手法を提案する。
まず、$mathsfThresholdedDeflatedtext-HeteroPCA$と呼ばれる新しいスペクトルアルゴリズムを使ってテンソル部分空間の推定を行い、続いてクラスタノードを取得するためにおよそ$k$-meansを実行する。
我々のアルゴリズムは、SNRが計算限界を超える限り、正確なクラスタリングを確実に達成する。
論文 参考訳（メタデータ） (2023-11-04T02:50:40Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳（メタデータ） (2023-02-13T19:57:17Z) - Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model [12.868722327487752]
行列値の観測を行うために低ランク混合モデル(LrMM)を提案する。
ロイドのアルゴリズムと低ランク近似を統合して計算効率のよいクラスタリング法を設計する。
本手法は,実世界のデータセットにおける文献上の他者よりも優れる。
論文 参考訳（メタデータ） (2022-07-11T03:16:10Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。
アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文 参考訳（メタデータ） (2021-06-04T16:37:19Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - Spectral Clustering using Eigenspectrum Shape Based Nystrom Sampling [19.675277307158435]
本稿では,新しいサンプリング手法であるCentroid Minimum Sum of Squared similarities (CMS3)と,それをいつ使用するかを示す,スケーラブルなNystromベースのクラスタリングアルゴリズムを提案する。
我々のデータセットはデータセットの固有スペクトル形状に依存しており、他の最先端手法と比較して、テストにおいて競合する低ランク近似が得られる。
論文 参考訳（メタデータ） (2020-07-21T17:49:03Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。