Continuum limit of total variation on point clouds

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 $\Gamma$-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 $\Gamma$-convergence to hold. Taking the limit is enabled by a transportation based metric which allows to suitably compare functionals defined on different point clouds.

References in corpus (3)

• Consistency of spectral clustering
• An Adaptive Total Variation Algorithm for Computing the Balanced Cut of a Graph
• Partial regularity and smooth topology-preserving approximations of rough domains

Cited by in corpus (36)

• A Sampling Theory Perspective of Graph-based Semi-supervised Learning
• Continuum Limit of Lipschitz Learning on Graphs
• Nonlocal-interaction equation on graphs: gradient flow structure and continuum limit
• The Total Variation Flow in Metric Random Walk Spaces
• Uniform Convergence Rates for Lipschitz Learning on Graphs
• Mumford-Shah functionals on graphs and their asymptotics
• A Graph Framework for Manifold-valued Data
• Discrete stochastic approximations of the Mumford-Shah functional
• Homogenization of random convolution energies in heterogeneous and perforated domains
• On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms
• Geometric structure of graph Laplacian embeddings
• Local Regularization of Noisy Point Clouds: Improved Global Geometric Estimates and Data Analysis
• $N^{3/4}$ law in the cubic lattice
• On a Class of Nonlocal Continuity Equations on Graphs
• The Geometry of Adversarial Training in Binary Classification
• Gradient Flows and Nonlinear Power Methods for the Computation of Nonlinear Eigenfunctions
• An MBO scheme for minimizing the graph Ohta-Kawasaki functional
• Least action principles for incompressible flows and geodesics between shapes
• Gamma-convergence of a nonlocal perimeter arising in adversarial machine learning
• A continuum limit for the PageRank algorithm
• Selberg integrals in 1D random Euclidean optimization problems
• Nonlocal $p$-Laplacian Variational problems on graphs
• Asymptotic behavior of the Dirichlet energy on Poisson point clouds
• $(BV,L^p)$-decomposition, $p=1,2$, of Functions in Metric Random Walk Spaces
• Variational limits of k-NN graph based functionals on data clouds
• On the Gamma convergence of functionals defined over pairs of measures and energy-measures
• Models for information propagation on graphs
• Hypergraph $p$-Laplacian regularization on point clouds for data interpolation
• Entropic Optimal Transport in Random Graphs
• On anisotropic diffusion equations for label propagation
• Limits and consistency of non-local and graph approximations to the Eikonal equation
• Multiview Sensing With Unknown Permutations: An Optimal Transport Approach
• A Linear Transportation ${\mathrm{L}}^p$ Distance for Pattern Recognition
• Random discretization of O'Hara knot energy
• Large data limit for a phase transition model with the p-Laplacian on point clouds
• PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds