Timezone: »

Convergence and Energy Landscape for Cheeger Cut Clustering
Xavier Bresson · Thomas Laurent · David Uminsky · James von Brecht

Mon Dec 03 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor #None

Unsupervised clustering of scattered, noisy and high-dimensional data points is an important and difficult problem. Continuous relaxations of balanced cut problems yield excellent clustering results. This paper provides rigorous convergence results for two algorithms that solve the relaxed Cheeger Cut minimization. The first algorithm is a new steepest descent algorithm and the second one is a slight modification of the Inverse Power Method algorithm \cite{pro:HeinBuhler10OneSpec}. While the steepest descent algorithm has better theoretical convergence properties, in practice both algorithm perform equally. We also completely characterize the local minima of the relaxed problem in terms of the original balanced cut problem, and relate this characterization to the convergence of the algorithms.

Author Information

Xavier Bresson (City University of Hong Kong)
Thomas Laurent (Loyola Marymount University)
David Uminsky (University of San Francisco)
James von Brecht (UCLA)

More from the Same Authors