Optimality of Spectral Clustering in the Gaussian Mixture Model
Spectral clustering is one of the most popular algorithms to group high dimensional data. It is easy to implement and computationally efficient. Despite its popularity and successful applications, its theoretical properties have not been fully understood. In this paper, we show that spectral clustering is minimax optimal in the Gaussian Mixture Model with isotropic covariance matrix, when the number of clusters is fixed and the signal-to-noise ratio is large enough. Spectral gap conditions are widely assumed in the literature to analyze spectral clustering. On the contrary, these conditions are not needed to establish optimality of spectral clustering in this paper.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Minimax-Optimal Dimension-Reduced Clustering for High-Dimensional Nonspherical Mixtures
In mixture models, nonspherical (anisotropic) noise within each cluster is widely present in real-world data. We study both the minimax rate and optimal statistical procedure for clustering under high-dimensional nonsphe…
ClusteringDimensionality ReductionClustering a Mixture of Gaussians with Unknown Covariance
We investigate a clustering problem with data from a mixture of Gaussians that share a common but unknown, and potentially ill-conditioned, covariance matrix. We start by considering Gaussian mixtures with two equally-si…
ClusteringAn $\ell_p$ theory of PCA and spectral clustering
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 precis…
ClusteringCommunity DetectionMAP Clustering under the Gaussian Mixture Model via Mixed Integer Nonlinear Optimization
We present a global optimization approach for solving the maximum a-posteriori (MAP) clustering problem under the Gaussian mixture model.Our approach can accommodate side constraints and it preserves the combinatorial st…
Clusteringglobal-optimizationOptimal Estimation and Computational Limit of Low-rank Gaussian Mixtures
Structural matrix-variate observations routinely arise in diverse fields such as multi-layer network analysis and brain image clustering. While data of this type have been extensively investigated with fruitful outcomes …
Image Clustering