Robustly Clustering a Mixture of Gaussians
  We give an efficient algorithm for robustly clustering of a mixture of two
arbitrary Gaussians, a central open problem in the theory of computationally
efficient robust estimation, assuming only that the the means of the component
Gaussians are well-separated or their covariances are well-separated. Our
algorithm and analysis extend naturally to robustly clustering mixtures of
well-separated strongly logconcave distributions. The mean separation required
is close to the smallest possible to guarantee that most of the measure of each
component can be separated by some hyperplane (for covariances, it is the same
condition in the second degree polynomial kernel). We also show that for
Gaussian mixtures, separation in total variation distance suffices to achieve
robust clustering. Our main tools are a new identifiability criterion based on
isotropic position and the Fisher discriminant, and a corresponding
Sum-of-Squares convex programming relaxation, of fixed degree.
