Skip to yearly menu bar Skip to main content


Poster

Convergence and Energy Landscape for Cheeger Cut Clustering

Xavier Bresson · Thomas Laurent · David Uminsky · James von Brecht

Harrah’s Special Events Center 2nd Floor

Abstract:

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.

Live content is unavailable. Log in and register to view live content