Cutoff for exact recovery of Gaussian mixture models

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.

References in corpus (5)

• Consistency of spectral clustering
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• Global analysis of Expectation Maximization for mixtures of two Gaussians
• On the tightness of an SDP relaxation of k-means
• Statistical Guarantees for Estimating the Centers of a Two-component Gaussian Mixture by EM

Cited by in corpus (1)

• Exact Recovery of Community Detection in k-Community Gaussian Mixture Model