Near-optimal-sample estimators for spherical Gaussian mixtures
  Statistical and machine-learning algorithms are frequently applied to
high-dimensional data. In many of these applications data is scarce, and often
much more costly than computation time. We provide the first sample-efficient
polynomial-time estimator for high-dimensional spherical Gaussian mixtures.
  For mixtures of any $k$ $d$-dimensional spherical Gaussians, we derive an
intuitive spectral-estimator that uses
$\mathcal{O}_k\bigl(\frac{d\log^2d}{\epsilon^4}\bigr)$ samples and runs in time
$\mathcal{O}_{k,\epsilon}(d^3\log^5 d)$, both significantly lower than
previously known. The constant factor $\mathcal{O}_k$ is polynomial for sample
complexity and is exponential for the time complexity, again much smaller than
what was previously known. We also show that
$\Omega_k\bigl(\frac{d}{\epsilon^2}\bigr)$ samples are needed for any
algorithm. Hence the sample complexity is near-optimal in the number of
dimensions.
  We also derive a simple estimator for one-dimensional mixtures that uses
$\mathcal{O}\bigl(\frac{k \log \frac{k}{\epsilon} }{\epsilon^2} \bigr)$ samples
and runs in time
$\widetilde{\mathcal{O}}\left(\bigl(\frac{k}{\epsilon}\bigr)^{3k+1}\right)$.
Our other technical contributions include a faster algorithm for choosing a
density estimate from a set of distributions, that minimizes the $\ell_1$
distance to an unknown underlying distribution.
