Near-optimal-sample estimators for spherical Gaussian mixtures

Many important distributions are high dimensional, and often they can be modeled as Gaussian mixtures. We derive the first sample-efficient polynomial-time estimator for high-dimensional spherical Gaussian mixtures. Based on intuitive spectral reasoning, it approximates mixtures of k spherical Gaussians in d-dimensions to within l1 distance e using O(dk9(log2 d)/e4) samples and Ok,e(d3 log5 d) computation time. Conversely, we show that any estimator requires Ω(dk/e2) samples, hence the algorithm's sample complexity is nearly optimal in the dimension. The implied time-complexity factor Ok,e is exponential in k, but much smaller than previously known. We also construct a simple estimator for one-dimensional Gaussian mixtures that uses O(k/e2) samples and O((k/e)3k+1) computation time.