The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
A Spectral Algorithm for Learning Mixtures of Distributions
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
We show that a simple spectral algorithm for learning a mixture of k spherical Gaussians in Rn works remarkably well — it succeeds in identifying the Gaussians assuming essentially the minimum possible separation between their centers that keeps them unique (solving an open problem of [1]). The sample complexity and running time are polynomial in both n and k. The algorithm also works for the more general problem of learning a mixture of "weakly isotropic" distributions (e.g. a mixture of uniform distributions on cubes).