Videos

Spectral Clustering Revisited

Presenter
October 31, 2013
Abstract
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.