Total Variation Clustering

Xavier Bresson
City University of Hong Kong

We introduce a new algorithm to solve the L1-relaxation of the Cheeger cut problem. The L2-relaxation, known as spectral clustering, only loosely relates to the Cheeger cut; however, it is convex and leads to a simple optimization problem. The L1-relaxation, in contrast, is non-convex but is provably equivalent to the original problem. The L1-relaxation therefore trades convexity for exactness, yielding improved clustering results at the cost of a more challenging optimization. The proposed L1 Cheeger algorithm is based on a steepest descent method that is guaranteed to converge.

Presentation (PDF File)

Back to Convex Relaxation Methods for Geometric Problems in Scientific Computing