An investigation of computational and informational limits in Gaussian mixture clustering
Lists
Only you see this
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...