Spectral Partitioning: approximations, image processing and clustering

Dave Tolliver

Abstract

I'll introduce the Cheeger inequality, a fundamental theoretical result relating the spectrum of a graph to the cost of various quotient cuts. Then I'll quickly introduce a few worst case examples and use similar technology to explain the behavior of spectral image segmentation algorithms. Finally, I'll introduce a family of partitioning methods, spectral rounding, and apply them to image segmentation tasks. Spectral rounding produces edge separators of a graph by iteratively reweighting the edges until the graph disconnects into the prescribed number of components. By directly producing discrete solutions we avoid the use of heuristic geometric separators (e.g. k-means) in obtaining the cut.

Back to the Main Page