When is Clustering Hard ?
of Work in Progress PASCAL Workshop on Statistics and Optimization of Clustering, July 2005 We propose questions regarding the informational and computational limits of learning a mixture of Gaussians—the sample sizes necessary in order to recover the generating mixture with unbounded, and bounded, computation. We would like to quantify the gap between the two, i.e. the excess information required for tractable estimation. We report on an empirical study attempting to shed light on these