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. kmeans) in obtaining the cut.

Pradeep Ravikumar Last modified: Mon Dec 4 10:15:44 EST 2006