Accession Number:

ADA612749

Title:

Convergence and Energy Landscape for Cheeger Cut Clustering

Descriptive Note:

Corporate Author:

CALIFORNIA UNIV LOS ANGELES DEPT OF MATHEMATICS

Report Date:

2014-12-01

Pagination or Media Count:

20.0

Abstract:

This paper provides both theoretical and algorithmic results for 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 first challenge is understanding convergence of algorithms. This paper provides the first complete proof of convergence for algorithms that minimize the 1-relaxation. The second challenge entails comprehending the l1- energy landscape, i.e. the set of possible points to which an algorithm might converge. We show that l1-algorithms can get trapped in local minima that are not globally optimal and we provide a classification theorem to interpret these local minima. This classification gives meaning to these suboptimal solutions and helps to explain, in terms of graph structure, when the l1-relaxation provides the solution of the original Cheeger cut problem.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE