2014 · 29 citations · 25 references
Natural SciencesComputer ScienceMathematicsAlgorithmsComputational GeometryStatisticsDensity EstimationStatistical InferenceComplexityGaussian Mixture ModelsSample ComplexitySample Complexity Analysis
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.
25
Mixture Densities, Maximum Likelihood and the EM Algorithm
Richard A. Redner, Homer F. Walker · SIAM Review · 1984 · 2.7K citations
Learning mixtures of Gaussians
Sanjoy Dasgupta · 2003 · 624 citations