CMU VASC seminar : Spectral Rounding: with Applications in Image Segmentation and Clustering

Title : Spectral Rounding: with Applications in Image Segmentation and Clustering

Presenter : David Tolliver

Abstract
I'll discuss a novel family of spectral partitioning methods. Edgeseparators of a graph are produced by iteratively reweighting the edges until the graph disconnects into the prescribed number of components. At each iteration a small number of eigenvectors with small eigenvalue arecomputed and used to determine the reweighting. In this way spectralrounding directly produces discrete solutions where as current spectralalgorithms must map the continuous eigenvectors to discrete solutions byemploying a heuristic geometric separator (\\eg k-means). We show thatspectral rounding compares favorably to current spectral approximations onthe Normalized Cut criterion (NCut). Results are given for natural imagesegmentation, medical image segmentation, and clustering. A simple versionis shown to converge.This is joint work with Gary Miller in the Computer Science Departmentat CMU.

More info about VASC seminar.