Georgia Institute of Technology College of Sciences

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. This problem has a rich history of study in both statistics and, more recently, in CS Theory and Machine Learning. We present a polynomial time algorithm for this problem (running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy), with provably minimal assumptions on the Gaussians. Prior to this work, it was unresolved whether such an algorithm was even information theoretically possible (ie, whether a polynomial amount of data, and unbounded computational power sufficed). One component of the proof is showing that noisy estimates of the low-order moments of a 1-dimensional mixture suffice to recover accurate estimates of the mixture parameters, as conjectured by Pearson (1894), and in fact these estimates converge at an inverse polynomial rate. The second component of the proof is a dimension-reduction argument for how one can piece together information from different 1-dimensional projections to yield accurate parameters.