Mixtures of gaussian (or normal) distributions are used to model distributions in many areas, including machine learning. Many hueristics have been proposed for the task of finding the component gaussians given samples from the mixture. The EM algorithm from 1977 is a well-known example. However, such heuristics are known to require time exponential in the dimension (i.e., number of variables) the worst case, even when the number of components is $2$.

This paper presents the first algorithm that provably learns the component gaussians in time that is polynomial in the dimension. The gaussians may have arbitrary shape provided they satisfy a ``nondegeneracy'' condition, which requires their high-probability regions to be not ``too close'' together. (This improves a partial result by Dasgupta in 1999, which applied to "spherelike" gaussians.)

Joint work with Ravi Kannan; to appear in ACM STOC 2001.