An investigation of computational and informational limits in Gaussian mixture clustering

Nathan Srebro, Gregory Shakhnarovich, Sam T. Roweis

Abstract

We investigate under what conditions clustering by learning a mixture of spherical Gaussians is (a) computationally tractable; and (b) statistically possible. We show that using principal component projection greatly aids in recovering the clustering using EM; present empirical evidence that even using such a projection, there is still a large gap between the number of samples needed to recover the clustering using EM, and the number of samples needed without computational restrictions; and characterize the regime in which such a gap exists.
BibTeX
@inproceedings{srebro2006investigation,
  author = {Nathan Srebro and Gregory Shakhnarovich and Sam T. Roweis},
  title = {{An investigation of computational and informational limits in Gaussian mixture clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2006},
  doi = {10.1145/1143844.1143953},
}

Loading related content...

Figure