A Fourier analytique approach to Gaussian mixture learning

Suppose that we are given independent, identically distributed random samples x1,cdots,xn from a mixture at most k many d-dimensional spherical Gaussian distributions μ1,cdots,μk0 of identical and known variance σ2 in each coordinate, such that the minimum ℓ2 distance between two distinct centers yl and yj is greater than 2Deltaσ min√d,√ k, where Delta>C0, and C0 is a sufficiently large universal constant. We develop a randomized algorithm that learns the centers yl's of the Gaussian components to within an ℓ2 distance of k-tilde C0 -- in presence of arbitrarily large number of components and in arbitrary dimension, when the weights are known to be uniform. Furthermore, if the number of components is k= Omega(2d), then for arbitrary universal constant c>0, even for unknown weights, the algorithm learns the centers to within an ℓ2 distance of d-tilde C0 and the weights up to an accuracy of cwmin, with probability greater than 1 - exp(-k/c), provided that the weights lie in [c/k,1/ck], and the minimum separation is just 2c√ d. The number of samples and the computational time is bounded above by poly(k, d) in either case. Such a bound on the sample and computational complexity was previously unknown in the regime of non-constant dimension, and in particular, when d is not O(1). When d = O(1), this complexity bound follows from work of Regev and Vijayaraghavan, where it has also been shown that the sample complexity of learning a random mixture of Gaussians in a ball of radius o(√d) in d dimensions, when d is Theta( log k), is at least super-polynomial in k, d, showing that our result is tight in this case.