PIRE - mathematics, mechanics, materials science

Science at the triple point between
mathematics, mechanics and materials science

Publication 86

Continuum Limit of Total Variation on Point Clouds

Authors:

CMUNicolás García Trillos
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213


CMUDejan Slepčev
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213


Abstract:
We consider point clouds obtained as random samples of a measure on a Euclidean domain. A graph representing the point cloud is obtained by assigning weights to edges based on the distance between the points they connect. Our goal is to develop mathematical tools needed to study the consistency, as the number of available data points increases, of graph-based machine learning algorithms for tasks such as clustering. In particular, we study when is the cut capacity, and more generally total variation, on these graphs a good approximation of the perimeter (total variation) in the continuum setting. We address this question in the setting of G-convergence. We obtain almost optimal conditions on the scaling, as number of points increases, of the size of the neighborhood over which the points are connected by an edge for the G-convergence to hold. Taking the limit is enabled by a new metric which allows to suitably compare functionals defined on different point clouds.
Get the paper in its entirety
14-CNA-024.pdf

Back to Publications