Learning mixtures of spherical Gaussians: moment methods and spectral decompositions

Citation

Authors: Daniel Hsu, Sham M. Kakade
Year: 2013
Venue: Proceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS 2013), 11-20
arXiv: arXiv:1206.5766
URL: https://www.cs.columbia.edu/~djhsu/papers/mog-arxiv.pdf

One-Line Takeaway

Hsu and Kakade show that spherical Gaussian mixtures are efficiently recoverable from low-order moments via a spectral decomposition when the component means are in general position, without imposing explicit separation assumptions.

Technical Summary

Setup: the model is $x \sim \sum_{i=1}^{k} w_i \,\mathcal N(\mu_i,\sigma_i^2 I),$ with $w_i>0$ and $\mathrm{rank}(A)=k$ for $A=[\mu_1|\cdots|\mu_k]\in\mathbb R^{d\times k}$ .
Observable-moment structure: if $\bar\sigma^2$ is the smallest eigenvalue of $\mathrm{Cov}(x)$ and $v$ is a corresponding unit eigenvector, then the denoised moments $M_2 = \mathbb E[x\otimes x]-\bar\sigma^2 I = \sum_i w_i\,\mu_i^{\otimes 2},$ $M_3 = \mathbb E[x^{\otimes 3}] - \text{Gaussian-noise correction} = \sum_i w_i\,\mu_i^{\otimes 3}$ expose the mixture as a rank- $k$ tensor decomposition.
Spectral recovery: for a generic probe vector $\eta$ with distinct nonzero $\eta^\top\mu_i$ , diagonalize $M_{\mathrm{GMM}}(\eta)=M_2^{\dagger 1/2} M_3(\eta) M_2^{\dagger 1/2},$ whose nonzero eigenpairs recover $\mu_i$ , then obtain $w_i$ and $\sigma_i^2$ from $M_1$ and $\mathbb E[x]$ .
Main guarantee: no explicit minimum-separation assumption is required; learnability follows from spherical noise plus the rank / general-position condition, with finite-sample error polynomial in $d,k,1/\epsilon$ and the conditioning of $M_2$ .

Assumptions And Limits

The result is for spherical covariance structure and depends on a general-position assumption on the means. It is not a full solution for arbitrary Gaussian mixtures with unrestricted covariances.

Relevance To This Project

This paper is useful because it isolates a structural regime where latent recovery becomes easy once the moment tensors have a simple enough geometry. In the x -> z -> y framing, it suggests a strategy for latent-strategy identification when the induced multi-view statistics expose a low-rank tensor with a well-conditioned decomposition.

Comparison Notes

Compared with Moitra and Valiant (2010), the assumptions are narrower but the algorithm is cleaner and more spectral. Compared with Allman et al. (2009), the paper is more explicitly algorithmic and moment-based.

Source Note

Retrieval: alphaXiv MCP get_paper_content on arXiv:1206.5766; no local cache or downloaded source artifacts were created.

Verified from source: title, authors, arXiv identifier, the explicit denoised moments $M_1,M_2,M_3$ , the diagonalization formula for $M_{\mathrm{GMM}}(\eta)$ , the rank- $k$ / positive-weight assumption, and the polynomial finite-sample guarantee were checked against the alphaXiv-extracted arXiv text.