Cutoff for Exact Recovery of Gaussian Mixture Models
Authors:
Open Access
- 2 March 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (6) , 4223-4238
Abstract
We determine the information-theoretic cutoff value on separation of cluster centers for exact recovery of cluster labels in a K-component Gaussian mixture model with equal cluster sizes. Moreover, we show that a semidefinite programming (SDP) relaxation of the K-means clustering method achieves such sharp threshold for exact recovery without assuming the symmetry of cluster centers.Keywords
All Related Versions
Funding Information
- NSF CAREER Award (DMS-1752614)
- UIUC Research Board Award (RB18099)
- Simons Fellowship
- NSF (DMS-1907316)
This publication has 48 references indexed in Scilit:
- Spectral AlgorithmsFoundations and Trends® in Theoretical Computer Science, 2009
- Consistency of spectral clusteringThe Annals of Statistics, 2008
- Phase transition of the largest eigenvalue for nonnull complex sample covariance matricesThe Annals of Probability, 2005
- Model-Based Clustering, Discriminant Analysis, and Density EstimationJournal of the American Statistical Association, 2002
- Adaptive estimation of a quadratic functional by model selectionThe Annals of Statistics, 2000
- Optimal Rate of Convergence for Finite Mixture ModelsThe Annals of Statistics, 1995
- The solution of some random NP-hard problems in polynomial expected timeJournal of Algorithms, 1989
- Stochastic blockmodels: First stepsSocial Networks, 1983
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982
- Strong Consistency of $K$-Means ClusteringThe Annals of Statistics, 1981