A spectral algorithm for learning mixture models

It is shown that a simple spectral algorithm for learning a mixture of k spherical Gaussians in Rn works remarkably well and succeeds in identifying the Gaussian assuming essentially the minimum possible separation between their centers that keeps them unique.

Abstract

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 Arora and Kannan (Proceedings of the 33rd ACM STOC, 2001). The sample complexity and running time are polynomial in both n and k. The algorithm can be applied to the more general problem of learning a mixture of "weakly isotropic" distributions (e.g. a mixture of uniform distributions on cubes).