Variational Limits of Graph Cuts on Point Clouds.pdf (6.47 MB)
0/0

Variational Limits of Graph Cuts on Point Clouds

Download (6.47 MB)
thesis
posted on 01.05.2015 by Nicolás Garcia Trillos

The main goal of this thesis is to develop tools that enable us to study the convergence of minimizers of functionals defined on point clouds towards minimizers of equivalent functionals in the continuum; the point clouds we consider are samples of a ground-truth distribution. In particular, 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 these cuts converge as the sample size increases to a minimizer of a corresponding continuum cut (which partitions the ground-truth distribution). 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 multi-way cuts. The results are obtained by using the notion of Γ-convergence and an appropriate choice of metric which allows us to compare functions defined on point clouds with functions defined on continuous domains.

History

Date

01/05/2015

Degree Type

Dissertation

Department

Mathematical Sciences

Degree Name

Doctor of Philosophy (PhD)

Advisor(s)

Dejan Slepčev

Exports

Exports