A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians

Sanjoy Dasgupta, Leonard Schulman.

Year: 2007, Volume: 8, Issue: 7, Pages: 203−226


We show that, given data from a mixture of k well-separated spherical Gaussians in d, a simple two-round variant of EM will, with high probability, learn the parameters of the Gaussians to near-optimal precision, if the dimension is high (d >> ln k). We relate this to previous theoretical and empirical work on the EM algorithm.