On Spectral Learning of Mixtures of Distributions

We consider the problem of learning mixtures of distributions via spectral methods and derive a characterization of when such methods are useful. Specifically, given a mixture-sample, let \({\bar{\mu }}_i,{\bar{C}}_i,{\bar{w}}_i\) denote the empirical mean, covariance matrix, and mixing weight of the samples from the i-th component. We prove that a very simple algorithm, namely spectral projection followed by single-linkage clustering, properly classifies every point in the sample provided that each pair of means \({\bar{\mu }}_i,{\bar{\mu }}_j\) is well separated, in the sense that \(\| {\bar{\mu }}_i-{\bar{\mu }}_j{\| }^2\) is at least \(\| {\bar{C}}_i{\| }_2(1/{\bar{w}}_i+1/{\bar{w}}_j)\) plus a term that depends on the concentration properties of the distributions in the mixture. This second term is very small for many distributions, including Gaussians, Log-concave, and many others. As a result, we get the best known bounds for learning mixtures of arbitrary Gaussians in terms of the required mean separation. At the same time, we prove that there are many Gaussian mixtures {(μ _i ,C _i ,w _i )} such that each pair of means is separated by ||C _i ||₂(1/w _i  + 1/w _j ), yet upon spectral projection the mixture collapses completely, i.e., all means and covariance matrices in the projected mixture are identical.