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
- 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?)
- A Polylogarithmic Approximation of the Minimum Bisection
- 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 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 MBO scheme on graphs for classification and image processing
- An exact combinatorial algorithm for minimum graph bisection
- An introduction to -convergence
- 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
- 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 GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
- The Generic Chaining
- 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
- \(\Gamma \)-convergence for nonlocal phase transitions
- \(\Gamma\)-convergence of graph Ginzburg-Landau functionals
Cited in
(72)- Continuation of point clouds via persistence diagrams
- An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
- Properly-weighted graph Laplacian for semi-supervised learning
- Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data
- Asymptotic analysis of the Ginzburg–Landau functional on point clouds
- Lipschitz regularity of graph Laplacians on random data clouds
- Consistency of Dirichlet partitions
- Introduction: Big data and partial differential equations
- Compactness by Coarse-Graining in long-range lattice systems
- Homogenization theory: periodic and beyond. Abstracts from the workshop held March 14--20, 2021 (online meeting)
- Discrete stochastic approximations of the Mumford-Shah functional
- \((\mathrm{BV},L^p)\)-decomposition, \(p = 1,2\), of functions in metric random walk spaces
- Fluctuation estimates for the multi-cell formula in stochastic homogenization of partitions
- Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
- An MBO scheme for minimizing the graph Ohta-Kawasaki functional
- Asymptotic behavior of the Dirichlet energy on Poisson point clouds
- Analysis of \(p\)-Laplacian regularization in semisupervised learning
- Entropic Optimal Transport on Random Graphs
- Deep limits of residual neural networks
- Consistency of modularity clustering on random geometric graphs
- The total variation flow in metric random walk spaces
- On a class of nonlocal continuity equations on graphs
- On the Gamma convergence of functionals defined over pairs of measures and energy-measures
- A variational approach to the consistency of spectral clustering
- Cahn–Hilliard equations on random walk spaces
- \(\Gamma\)-limit of the cut functional on dense graph sequences
- Continuum limits of nonlocal \(p\)-Laplacian variational problems on graphs
- Discrete-to-continuum limits of multibody systems with bulk and surface long-range interactions
- Nonlocal-interaction equation on graphs: gradient flow structure and continuum limit
- Continuum limit of p-Laplacian evolution problems on graphs: Lq graphons and sparse graphs
- A maximum principle argument for the uniform convergence of graph Laplacian regressors
- A Graph Framework for Manifold-Valued Data
- Continuum limits of posteriors in graph Bayesian inverse problems
- From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
- Local regularization of noisy point clouds: improved global geometric estimates and data analysis
- scientific article; zbMATH DE number 7255037 (Why is no real title available?)
- \(N^{3/4}\) law in the cubic lattice
- Least action principles for incompressible flows and geodesics between shapes
- A compactness theorem for functions on Poisson point clouds
- Variational limits of \(k\)-NN graph-based functionals on data clouds
- Theoretical Analysis of Active Contours on Graphs
- Analysis and algorithms for \(\ell_p\)-based semi-supervised learning on graphs
- Eikonal depth: an optimal control approach to statistical depths
- Consistency of Cheeger and ratio graph cuts
- Entropy dissipation of Fokker-Planck equations on graphs
- Gromov-Hausdorff limit of Wasserstein spaces on point clouds
- Modeling self-aggregation of stochastic particles: a \(\Gamma\)-convergence approach
- A transportation \(L^p\) distance for signal analysis
- Spectral analysis of weighted Laplacians arising in data clustering
- scientific article; zbMATH DE number 62636 (Why is no real title available?)
- Variational homogenization: old and new
- Estimating perimeter using graph cuts
- \(\varGamma\)-convergence of nonlocal Dirichlet energies with penalty formulations of Dirichlet boundary data
- Large data and zero noise limits of graph-based semi-supervised learning algorithms
- Gradient flows in metric random walk spaces
- Rates of convergence for Laplacian semi-supervised learning with low labeling rates
- Mumford-Shah functionals on graphs and their asymptotics
- An extension theorem from connected sets and homogenization of non-local functionals
- CURE: curvature regularization for missing data recovery
- Homogenization of random convolution energies
- Convex variational methods on graphs for multiclass segmentation of high-dimensional data and point clouds
- Homogenization of ferromagnetic energies on Poisson random sets in the plane
- Sharp \(N^{3/4}\) law for the minimizers of the edge-isoperimetric problem on the triangular lattice
- Continuum limit of Lipschitz learning on graphs
- Structure-preserving deep learning
- Harmonic Extension on The Point Cloud
- A continuum limit for the PageRank algorithm
- Optimal Cheeger cuts and bisections of random geometric graphs
- A new analytical approach to consistency and overfitting in regularized empirical risk minimization
- On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms
- Large data limit for a phase transition model with the p-Laplacian on point clouds
- Partial differential equations and variational methods for geometric processing of images
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)
