loading...
A Spectral Algorithm for Learning Mixtures of Distributions
Vancouver, BC, Canada November 16-November 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181888The 43rd Annual IEEE Symposium on Fou ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Santosh Vempala, Massachusetts Institute of Technology
Grant Wang, Massachusetts Institute of Technology
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.