A Fourier analytique approach to Gaussian mixture learning

Suppose that we are given independent, identically distributed random samples x_1,\cdots,x_n from a mixture at most k many d-dimensional spherical Gaussian distributions μ_1,\cdots,μ_{k_0} of identical and known variance σ^2 in each coordinate, such that the minimum \ell^2 distance between two distinct centers y_l and y_j is greater than 2Δσ\min{\sqrt{d},\sqrt k}, where Δ>C_0, and C_0 is a sufficiently large universal constant. We develop a randomized algorithm that learns the centers y_l's of the Gaussian components to within an \ell^2 distance of k^{-\tilde C_0} -- 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= Ω(2^d), then for arbitrary universal constant c>0, even for unknown weights, the algorithm learns the centers to within an \ell^2 distance of d^{-\tilde C_0} and the weights up to an accuracy of cw_{min}, 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\sqrt 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(\sqrt{d}) in d dimensions, when d is Θ( \log k), is at least super-polynomial in k, d, showing that our result is tight in this case.