Tuesday / Theory Seminar

October 13 / 1:00pm

Mudd 3514

Speaker: Ravi Kannan

Talk Title: Learning Mixtures with separation based on latent dimension

Abstract:

There is a rich literature on learning mixture distributions assuming separation of componnt means based on the number of clusters k and the ambient dimension d. There are many application areas in which the means of the clusters lie in an m dimensional sub-space with m << k. Addressing this point, we prove that a separation depending upon m (the dependence on m being ? m) suffices and indeed the classical SVD-based algorithm ("project to m dimensional SVD space and cluster in the projection") learns under this separation provided the matrix of means has a high enough m th singular value. The proof uses the "sine theta" theorem which bounds the sensitivity of singular space. Our lower bound on the m th singular value, we prove is satisfied in a natural Bayesian mixture learning set-up, where a prior is assumed on the set of means. We also prove that under the separation assumption, we get a perfect clustering of the sample.