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.
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: