A spectral algorithm for learning mixtures of distributions

Abstract

We show that a simple spectral algorithm for learning a mixture of k spherical Gaussians in /spl Ropf//sup n/ works remarkably well - it succeeds in identifying the Gaussians assuming essentially the minimum possible separation between their centers that keeps them unique. 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).