Source-linked AI summary
Continuum limit of total variation on point clouds
Nicolás García Trillos, Dejan Slepčev
TL;DR
The paper asks when graph-based cuts and total variation on random point clouds consistently approximate continuum perimeter and total variation. It uses Γ-convergence in a transportation-based TL1 topology and proves convergence under scaling conditions, together with compactness and perimeter results. The framework provides a variational route for analyzing consistency of graph-based clustering and related algorithms.
Problem
The paper addresses when graph cut capacity and total variation on increasingly large random point clouds approximate continuum perimeter and total variation, supporting consistency analysis for graph-based learning.
Method
The paper compares graph and continuum functionals using Γ-convergence in the transportation-based TL1 topology, with transportation maps linking empirical and continuum measures.
Results
The scaled graph total variation Γ-converges to weighted continuum total variation, and restricting to characteristic functions yields Γ-convergence of graph perimeters to weighted continuum perimeters.
Takeaways & Limitations
The framework supports convergence of graph minimizers and minimum energies and supplies mathematical tools for studying consistency of graph-based clustering and related tasks.
Takeaways & Limitations
The TLp metric space is not complete, and the authors caution that some machine-learning settings may require convergence analyses beyond the presented results.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
The paper develops a Γ-convergence framework for determining when graph-based total variation and perimeter approximate their continuum counterparts on increasingly large random point clouds. It identifies a transportation-based topology and scaling conditions that support convergence, compactness, and consistency implications for clustering.
- Graph cuts and total variation are studied as approximations of continuum perimeter for data sampled independently from a measure with density ρ on D.The graph connects sufficiently close points with distance-based weights, while the continuum target is weighted by ρ^2.
- The TL1 topology uses transportation maps to compare functions supported on different point clouds with continuum functions.The empirical measure is transported to the sampling measure, allowing graph functionals to be compared across changing domains.
- Theorem 1.1 establishes Γ-convergence of graph total variation to σηTV(·,ρ^2) in the TL1 sense under the stated domain, density, kernel, and scaling assumptions.This variational convergence supports convergence of minimizers and minimum energies when the associated compactness property holds.
- Uniformly bounded L1 norms and graph total variations imply TL1-relative compactness of the corresponding function sequence.This compactness result supplies the key variational control needed alongside Γ-convergence.
- The scaled graph perimeter Γ-converges to the weighted continuum perimeter when functionals are restricted to characteristic functions.For a set A_n, GTVn,εn(χA_n) equals (1/(n^2ε_n))GPer(A_n).
- For constant density, the results reduce to appropriately scaled convergence of graph total variation and graph perimeter to the usual continuum quantities.The same scaling framework also yields pointwise convergence, with a stated improvement over an earlier rate.
- The compactness threshold is essentially sharp in dimensions d≥3, while taking ε_n below the connectivity scale can prevent compactness and produce disconnected-graph minimizers unlike continuum minimizers.The paper notes that some machine-learning settings may still require additional analysis beyond the presented convergence results.
2. PRELIMINARIES
The preliminaries define weighted variation and perimeter, then introduce optimal-transport distances and transportation maps for comparing measures and empirical samples. Matching estimates quantify how closely random points can be coupled to grids, with dimension-dependent behavior.
- Weighted total variation TV(u;ψ) defines weighted perimeter by Per(E;ψ) = TV(χE;ψ) for measurable sets.
- When ψ is bounded above and below by positive constants, weighted and unweighted L1 and BV spaces coincide with equivalent norms.
- The p-OT distance compares probability measures through couplings, with the p = 2 case also known as the Wasserstein distance.
- Stagnating transportation plans have vanishing average displacement and characterize weak convergence on bounded domains.
- Transportation maps push a source measure forward to an empirical measure and induce transportation plans used to compare the two distributions.
- In d = 2, the ∞-transportation distance between random points and grid points is of order (log n)^3/4, while matching behavior differs across dimensions.
3. THE SPACE TLp
TLp equips functions carried by varying measures with a transportation-based metric, allowing graph functions and continuum functions to be compared. Its completion is a larger probability-measure space, while convergence recovers familiar function and measure convergence in appropriate cases.
- The TLp distance is equivalent to a p-OT distance between graph measures and makes (TLp,dTLp) a metric space.
- TLp identifies a pair (μ,f) with a probability measure on D × R supported on the graph of f.
- The space TLp is not complete: a Cauchy sequence built from increasingly oscillatory functions need not converge within TLp.
- The completion of (TLp,dTLp) is (Pp(D × R),dp), obtained by approximating convex combinations of Dirac masses.
- For absolutely continuous μ, the closure of the TLp fiber over μ equals Pp(D × R) restricted to measures with first marginal μ.
- TLp convergence generalizes weak convergence of measures and Lp convergence of functions, and fixed-measure Lp convergence is equivalent to p-OT convergence of graph measures.
4. Γ-CONVERGENCE OF TVε(·,ρ)
The nonlocal functionals TVε(·;ρ) Γ-converge to weighted total variation, while the proof also establishes compactness and pointwise convergence under the stated domain and density assumptions.
- Theorem 4.1 establishes Γ-convergence of TVε(·;ρ) to σηTV(·,ρ2) in the L1(D,ρ)-metric.The domain is open and bounded with Lipschitz boundary, and ρ is continuous and bounded above and below by positive constants.
- The proof establishes compactness for {TVε(·;ρ)}ε>0 in the same L1(D,ρ)-metric.This compactness result handles domain-boundary effects and the absence of L∞ control.
- Liminf inequality: Regularization by mollification supplies the smoothness needed for the liminf argument without increasing the limiting energy.The regularized functions are smooth, and the regularization is controlled through the mollifier and interior domains.
- Liminf inequality: The liminf proof treats Lipschitz densities first and then approximates continuous densities from below by Lipschitz functions.The approximating densities preserve the same positive upper and lower bounds and converge monotonically to ρ.
- Limsup inequality: The limsup proof uses smooth approximation and extension from D to R^d to construct recovery sequences for weighted total variation.For Lipschitz-boundary domains, BV functions admit extensions whose boundary variation is controlled.
- The functionals also converge pointwise for every u∈L1(D,ρ).This follows from the liminf and limsup inequalities.
5. Γ-CONVERGENCE OF TOTAL VARIATION ON GRAPHS
Using transportation maps to compare empirical and continuum domains, the paper proves Γ-convergence of graph total variation to weighted continuum total variation and derives compactness and perimeter convergence.
- Theorem 1.1: Under the theorem’s assumptions, GTVn,εn Γ-converges in TL1 to σηTV(·,ρ2).The proof uses transportation maps whose displacement is small relative to εn.
- Theorem 1.1: The liminf and limsup inequalities are obtained by comparing graph interactions through transportation maps and approximating kernels by step functions.Piecewise-constant kernels are handled first, followed by monotone approximation for general kernels satisfying (K1)-(K3).
- Theorem 1.2: Uniformly bounded L1 norms and graph total variations imply relative compactness in TL1.After composition with transportation maps, the sequence is relatively compact in L1(D).
- Corollary 1.3: The scaled graph perimeters Γ-converge to the continuum weighted perimeter when functionals are restricted to characteristic functions.The proof uses the coarea formula to convert recovery sequences for functions into recovery sequences for sets.
- Extensions: Tighter transportation bounds for more regular or deterministic point sets would yield better admissible bounds on ε(n).The proof requires only an upper bound on the ∞-transportation distance between ν and νn.
- Extensions: For regularly spaced grid points in (0,1)^d, Γ-convergence holds when εn→0 and 1/(n1/dεn)→0.In this case the transportation estimate uses f(n)=1.
APPENDIX A. PROOF OF PROPOSITION 2.4
The appendix proves the weighted BV approximation result by reducing general weights to Lipschitz approximations and using smooth function sequences with convergent weighted variation.
- Weighted BV approximation: For smooth weighted-variation approximation, the proof first uses the result for Lipschitz weights.The Lipschitz case is identified with an existing approximation theorem.
- Weighted BV approximation: A general positive bounded weight is approximated by Lipschitz functions ψk that decrease pointwise to ψ.The approximating weights retain the same upper and lower bounds as ψ.
- Weighted BV approximation: For each approximating weight, smooth functions converge in L1(D) and their weighted gradient integrals converge to the corresponding total variation.A diagonal argument selects one sequence that works as k and n vary.
- Weighted BV approximation: The final sequence satisfies convergence of weighted gradient integrals to TV(u;ψ).The inequality ψ≤ψkn transfers the approximation from ψkn to ψ.