Continuum limit of total variation on point clouds
This provides theoretical foundations for graph-based algorithms in machine learning, but it is incremental as it builds on existing convergence frameworks.
The paper tackles the problem of ensuring that graph-based machine learning algorithms, such as for clustering, are consistent as data points increase, by studying when total variation on graphs approximates perimeter in the continuum. They establish almost optimal conditions for Γ-convergence using a transportation-based metric.
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 $Γ$-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 $Γ$-convergence to hold. Taking the limit is enabled by a transportation based metric which allows to suitably compare functionals defined on different point clouds.