Continuum limit of total variation on point clouds
From MaRDI portal
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 -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.
Recommendations
- Variational limits of \(k\)-NN graph-based functionals on data clouds
- A variational approach to the consistency of spectral clustering
- Consistency of Cheeger and ratio graph cuts
- Continuum limits of nonlocal p-Laplacian variational problems on graphs
- Gromov-Hausdorff limit of Wasserstein spaces on point clouds
Cites work
- \(\Gamma \)-convergence for nonlocal phase transitions
- \(\Gamma\)-convergence of graph Ginzburg-Landau functionals
- A first course in Sobolev spaces
- A new approach to Sobolev spaces and connections to \(\Gamma\)-convergence
- A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies
- A Polylogarithmic Approximation of the Minimum Bisection
- A quantitative description of mesh dependence for the discretization of singularly perturbed nonconvex problems
- A strong law for the longest edge of the minimal spanning tree
- An exact combinatorial algorithm for minimum graph bisection
- An introduction to -convergence
- An MBO scheme on graphs for classification and image processing
- Balanced graph partitioning
- Consistency of spectral clustering
- Continuous limits of discrete perimeters
- Diffuse Interface Models on Graphs for Classification of High Dimensional Data
- Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
- Expander flows, geometric embeddings and graph partitioning
- Finite difference approximation of the Mumford-Shah functional
- Finite-difference approximation of free-discontinuity problems
- Finsler structure in the \(p\)-Wasserstein space and gradient flows
- From graph to manifold Laplacian: the convergence rate
- Gradient flows in metric spaces and in the space of probability measures
- How the result of graph clustering methods depends on the construction of the graph
- scientific article; zbMATH DE number 2134074 (Why is no real title available?)
- scientific article; zbMATH DE number 3554969 (Why is no real title available?)
- scientific article; zbMATH DE number 1254188 (Why is no real title available?)
- scientific article; zbMATH DE number 2134813 (Why is no real title available?)
- scientific article; zbMATH DE number 1865939 (Why is no real title available?)
- scientific article; zbMATH DE number 1909499 (Why is no real title available?)
- scientific article; zbMATH DE number 1448982 (Why is no real title available?)
- Learning Theory
- Minimax grid matching and empirical measures
- Multi-class transductive learning based on \(\ell^1\) relaxations of Cheeger cut and Mumford-Shah-Potts model
- On optimal matchings
- On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
- On the Volume of Tubes
- Parametrized measures and variational principles
- Partial regularity and smooth topology-preserving approximations of rough domains
- Sharp thresholds for monotone properties in random geometric graphs
- The Generic Chaining
- THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
- The integrability of the square exponential transportation cost
- The normalized graph cut and Cheeger constant: from discrete to continuous
- The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
- Threshold dynamics for networks with arbitrary surface tensions
- Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
- Towards a theoretical foundation for Laplacian-based manifold methods
- Upper and lower bounds for stochastic processes. Modern methods and classical problems
- Weighted BV functions
Cited in
(90)- Consistency of modularity clustering on random geometric graphs
- Entropy dissipation of Fokker-Planck equations on graphs
- Convex variational methods on graphs for multiclass segmentation of high-dimensional data and point clouds
- A transportation \(L^p\) distance for signal analysis
- Gromov-Hausdorff limit of Wasserstein spaces on point clouds
- Continuation of point clouds via persistence diagrams
- An extension theorem from connected sets and homogenization of non-local functionals
- Properly-weighted graph Laplacian for semi-supervised learning
- Nonlocal-interaction equation on graphs: gradient flow structure and continuum limit
- An MBO scheme for minimizing the graph Ohta-Kawasaki functional
- Homogenization of ferromagnetic energies on Poisson random sets in the plane
- Fluctuation estimates for the multi-cell formula in stochastic homogenization of partitions
- Gradient flows in metric random walk spaces
- Homogenization theory: periodic and beyond. Abstracts from the workshop held March 14--20, 2021 (online meeting)
- From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
- Analysis and algorithms for \(\ell_p\)-based semi-supervised learning on graphs
- \((\mathrm{BV},L^p)\)-decomposition, \(p = 1,2\), of functions in metric random walk spaces
- Partial differential equations and variational methods for geometric processing of images
- On the Gamma convergence of functionals defined over pairs of measures and energy-measures
- The total variation flow in metric random walk spaces
- Least action principles for incompressible flows and geodesics between shapes
- \(N^{3/4}\) law in the cubic lattice
- Discrete stochastic approximations of the Mumford-Shah functional
- Optimal Cheeger cuts and bisections of random geometric graphs
- Spectral analysis of weighted Laplacians arising in data clustering
- Deep limits of residual neural networks
- Rates of convergence for Laplacian semi-supervised learning with low labeling rates
- Continuum limit of Lipschitz learning on graphs
- Consistency of Cheeger and ratio graph cuts
- Theoretical Analysis of Active Contours on Graphs
- Introduction: Big data and partial differential equations
- A new analytical approach to consistency and overfitting in regularized empirical risk minimization
- Continuum limits of posteriors in graph Bayesian inverse problems
- scientific article; zbMATH DE number 62636 (Why is no real title available?)
- Consistency of Dirichlet partitions
- Harmonic Extension on The Point Cloud
- A Graph Framework for Manifold-Valued Data
- Homogenization of random convolution energies
- scientific article; zbMATH DE number 7255037 (Why is no real title available?)
- On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms
- Structure-preserving deep learning
- Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data
- Variational limits of \(k\)-NN graph-based functionals on data clouds
- A maximum principle argument for the uniform convergence of graph Laplacian regressors
- Lipschitz regularity of graph Laplacians on random data clouds
- Large data limit for a phase transition model with the p-Laplacian on point clouds
- A continuum limit for the PageRank algorithm
- \(\Gamma\)-limit of the cut functional on dense graph sequences
- Continuum limits of nonlocal p-Laplacian variational problems on graphs
- Mumford-Shah functionals on graphs and their asymptotics
- Discrete-to-continuum limits of multibody systems with bulk and surface long-range interactions
- CURE: curvature regularization for missing data recovery
- Local regularization of noisy point clouds: improved global geometric estimates and data analysis
- Analysis of p-Laplacian regularization in semisupervised learning
- Estimating perimeter using graph cuts
- Asymptotic analysis of the Ginzburg–Landau functional on point clouds
- Continuum limit of p-Laplacian evolution problems on graphs: Lq graphons and sparse graphs
- A compactness theorem for functions on Poisson point clouds
- An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
- Entropic Optimal Transport on Random Graphs
- Cahn–Hilliard equations on random walk spaces
- Asymptotic behavior of the Dirichlet energy on Poisson point clouds
- Variational homogenization: old and new
- Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
- Eikonal depth: an optimal control approach to statistical depths
- On a class of nonlocal continuity equations on graphs
- Modeling self-aggregation of stochastic particles: a \(\Gamma\)-convergence approach
- -convergence of nonlocal Dirichlet energies with penalty formulations of Dirichlet boundary data
- Sharp \(N^{3/4}\) law for the minimizers of the edge-isoperimetric problem on the triangular lattice
- Evolution equations on co-evolving graphs: long-time behaviour and the graph-continuity equation
- Relaxation for a degenerate functional with linear growth in the onedimensional case
- Models for information propagation on graphs
- Singularities in discrete systems. Abstracts from the workshop held May 4--9, 2025
- Scaling limit of the Kuramoto model on random geometric graphs
- Continuum limit of p-biharmonic equations on graphs
- Covering one point process with another
- On metrics for analysis of functional data on geometric domains
- Hypergraph p-Laplacian regularization on point clouds for data interpolation
- Discrete-to-continuum rates of convergence for nonlocal p-Laplacian evolution problems
- A new perspective on denoising based on optimal transport
- Graph-to-local limit for the nonlocal interaction equation
- Selberg integrals in 1D random Euclidean optimization problems
- A variational approach to the consistency of spectral clustering
- On De Giorgi's conjecture of nonlocal approximations for free-discontinuity problems: the symmetric gradient case
- Phase synchronization in random geometric graphs on the two-dimensional sphere
- A nonlocal p-Laplacian interface model with sharp interface
- Convergence of graph Dirichlet energies and graph Laplacians on intersecting manifolds of varying dimensions
- Oriented point-cloud varifolds for estimating the perimeter and computing its Wasserstein gradient flow
- Large data and zero noise limits of graph-based semi-supervised learning algorithms
- Compactness by Coarse-Graining in long-range lattice systems
This page was built for publication: Continuum limit of total variation on point clouds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q261295)
