Spectral Clustering Revisited

Thursday, October 31, 2013 - 3:15pm - 4:05pm
Keller 3-180
Misha Belkin (The Ohio State University)
Methods for grouping data based on eigenvectors of the graph Laplacian have gained significant popularity due to their
strong empirical performance and amenability to theoretical analysis.
However, while algorithms for bi-partitioning are very simple and well-understood,
the situation with multi-way clustering is more complicated. Typical methods rely on k-means clustering or similar methods
whose performance significantly depends on initialization.

In this talk I will take a look at the problem of spectral clustering from a different angle,
by using ideas of geometric recovery related to those of Independent Component Analysis.
It turns out that due to the special nature of the clustering problem we can provide a large set of
constrast function with theoretical guarantees for clustering.
I will discuss the theoretical results, practical algorithms and some applications.

Joint work with Luis Rademacher and James Voss.