An investigation of computational and informational limits in Gaussian mixture clustering
Nathan Srebro, Gregory Shakhnarovich, Sam T. Roweis · 2006
We investigate under what conditions clus-tering 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 re-cover the clustering using EM, and the num-ber of samples needed without computational restrictions; and characterize the regime in which such a gap exists. 1.