Cutoff for exact recovery of Gaussian mixture models
Preprint
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
This publication has 33 references indexed in Scilit:
- Diffusion K-means clustering on manifolds: Provable exact recovery via semidefinite relaxationsApplied and Computational Harmonic Analysis, 2021
- Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits2021
- When do birds of a feather flock together? k-Means, proximity, and conic programmingMathematical Programming, 2018
- Clustering subgaussian mixtures by semidefinite programmingInformation and Inference: A Journal of the IMA, 2017
- Recovery guarantees for exemplar-based clusteringInformation and Computation, 2015
- Spectral redemption in clustering sparse networksProceedings of the National Academy of Sciences, 2013
- Introduction to the non-asymptotic analysis of random matrices2012
- 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