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).
Citation:
Santosh Vempala, Grant Wang, "A Spectral Algorithm for Learning Mixtures of Distributions," focs, pp.113, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||