Near-optimal-sample estimators for spherical Gaussian mixtures

Understand

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.