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.
Copyright. All Rights Reserved.