Cutoff for exact recovery of Gaussian mixture models

Authors:
  • XCXiaohui Chen
    Xiaohui Chen
  • YYYun Yang
    Yun Yang

Abstract
We determine the 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.