One-Pass Sparsified Gaussian Mixtures
  We present a one-pass sparsified Gaussian mixture model (SGMM). Given $N$
data points in $P$ dimensions, $X$, the model fits $K$ Gaussian distributions
to $X$ and (softly) classifies each point to these clusters. After paying an
up-front cost of $\mathcal{O}(NP\log P)$ to precondition the data, we subsample
$Q$ entries of each data point and discard the full $P$-dimensional data. SGMM
operates in $\mathcal{O}(KNQ)$ time per iteration for diagonal or spherical
covariances, independent of $P$, while estimating the model parameters in the
full $P$-dimensional space, making it one-pass and hence suitable for streaming
data. We derive the maximum likelihood estimators for the parameters in the
sparsified regime, demonstrate clustering on synthetic and real data, and show
that SGMM is faster than GMM while preserving accuracy.
