Abstract

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 distance   using samples and Ok, computation time. Conversely, we show that any estimator requires samples, hence the algorithm’s sample complexity is nearly optimal in the dimension. The implied time-complexity factor is exponential in k, but much smaller than previously known. We also construct a simple estimator for one-dimensional Gaussian mixtures that  uses samples and computation time.