Title:	A Spectral Algorithm for Learning General Gaussian Mixtures
Frank McSherry, MSR SVC (joint work with Dimitris Achlioptas, MSR 
Redmond)

Mixtures of Gaussians are a fundamental type of distribution used to 
model many real world data sets. A mixture of k Gaussians is defined by 
k mixing weights w_i, k mean vectors \mu_i, and k covariance matrices 
C_i^2. A sample is produced by selecting an index i with probability 
proportional to w_i, and then producing a Gaussian sample from the 
associated mean and covariance. One very natural and relevant problem 
is to infer the parameters {(w_i, \mu_i, C_i^2}) of a mixture of k 
Gaussians from observed data, with clear applications to machine 
learning and data mining.

Until recently, algorithms for learning mixtures of Gaussians were 
heuristic, employing local search techniques such as the EM algorithm. 
Work starting with Dasgupta, and continuing with Dasgupta and Schulman, 
and Arora and Kannan, conducts a rigorous analysis of learning mixtures 
of Gaussians, specifically in the context of random projections. 
Recently, Vempala and Wang observed that these techniques can be much 
improved in the case of spherical Gaussians (when C_i^2 ~ I) by first 
projecting the data onto the span of the top k singular vectors of the 
mixture's covariance matrix, but left open the question of the utility 
of spectral methods for mixtures of Gaussians with general covariance 
matrices.

In this talk, we use the perturbation theory of low rank matrices to 
give a compact proof that spectral projection is useful in the context 
of general gaussian mixtures, and more generally for mixtures of 
distributions whose covariance matrices have small 2-norm.  With the 
perturbation result in hand, we apply the simple and surprisingly 
useful Single-Linkage algorithm to cluster the projected data. Finally, 
time permitting we consider a lower bound for spectral projection that 
indicates that our analysis is tight, up to constant factors.