One-Pass Sparsified Gaussian Mixtures
This is an incremental improvement for streaming data applications, enabling faster clustering without sacrificing performance.
The paper tackles the problem of fitting Gaussian mixture models to high-dimensional data by introducing a one-pass sparsified method that reduces computational cost from O(KNP) to O(KNQ) per iteration, independent of dimension P, while maintaining accuracy comparable to standard GMM.
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.