Publication 14-CNA-029
Consistency of Cheeger and Ratio Graph Cuts
Nicolas García Trillos
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213
ngarciat@andrew.cmu.edu
Dejan Slepčev
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213
slepcev@andrew.cmu.edu
James Von Brecht
Department of Mathematics and Statistics
California State University
Long Beach, Ca 90840, USA
james.vonbrecht@csulb.edu
Thomas Laurent
Department of Mathematics
Loyola Marymount University
Los Angeles, Ca 90045, USA
thomas.laurent@lmu.edu
Xavier Bresson
Institute of Electrical Engineering
Swiss Federal Institute Of Technology (Epfl)
1015 Lausanne, Switzerland
xavier.bresson@epfl.ch
Abstract: This paper establishes the consistency of a family of
graph-cut-based algorithms for clustering of data clouds. We consider
point clouds obtained as samples of a ground-truth measure. We
investigate approaches to clustering based on minimizing objective
functionals defined on proximity graphs of the given sample. Our focus
is on functionals based on graph cuts like the Cheeger and ratio cuts.
We show that minimizers of the these cuts converge as the sample size
increases to a minimizer of a corresponding continuum cut (which
partitions the ground truth measure). Moreover, we obtain sharp
conditions on how the connectivity radius can be scaled with respect to
the number of sample points for the consistency to hold. We provide
results for two-way and for multiway cuts. Furthermore we provide
numerical experiments that illustrate the results and explore the
optimality of scaling in dimension two.
Get the paper in its entirety as 14-CNA-029.pdf
« Back to CNA Publications