skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: From Graph Cuts to Isoperimetric Inequalities: Convergence Rates of Cheeger Cuts on Data Clouds
Abstract In this work we study statistical properties of graph-based clustering algorithms that rely on the optimization of balanced graph cuts, the main example being the optimization of Cheeger cuts. We consider proximity graphs built from data sampled from an underlying distribution supported on a generic smooth compact manifold$${\mathcal {M}}$$ M . In this setting, we obtain high probability convergence rates for both the Cheeger constant and the associated Cheeger cuts towards their continuum counterparts. The key technical tools are careful estimates of interpolation operators which lift empirical Cheeger cuts to the continuum, as well as continuum stability estimates for isoperimetric problems. To the best of our knowledge the quantitative estimates obtained here are the first of their kind.  more » « less
Award ID(s):
1912802
PAR ID:
10366829
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Archive for Rational Mechanics and Analysis
Volume:
244
Issue:
3
ISSN:
0003-9527
Format(s):
Medium: X Size: p. 541-598
Size(s):
p. 541-598
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract We prove that if a parabolic Lipschitz (i.e., Lip(1,1/2)) graph domain has the property that its caloric measure is parabolic$$A_{\infty }$$ A with respect to surface measure (which property is in turn equivalent to$$\mathrm{L}^{p}$$ L p solvability of the Dirichlet problem for some finite$$p$$ p ), then the function defining the graph has a half-order time derivative in the space of (parabolic) bounded mean oscillation. Equivalently, we prove that the$$A_{\infty }$$ A property of caloric measure implies, in this case, that the boundary is parabolic uniformly rectifiable. Consequently, by combining our result with the work of Lewis and Murray we resolve a long standing open problem in the field by characterizing those parabolic Lipschitz graph domains for which one has$$\mathrm{L}^{p}$$ L p solvability (for some$$p <\infty $$ p < ) of the Dirichlet problem for the heat equation. The key idea of our proof is to view the level sets of the Green function as extensions of the original boundary graph for which we can prove (local) square function estimates of Littlewood-Paley type. 
    more » « less
  2. Abstract We introduce a family of Finsler metrics, called the$$L^p$$ L p -Fisher–Rao metrics$$F_p$$ F p , for$$p\in (1,\infty )$$ p ( 1 , ) , which generalizes the classical Fisher–Rao metric$$F_2$$ F 2 , both on the space of densities$${\text {Dens}}_+(M)$$ Dens + ( M ) and probability densities$${\text {Prob}}(M)$$ Prob ( M ) . We then study their relations to the Amari–C̆encov$$\alpha $$ α -connections$$\nabla ^{(\alpha )}$$ ( α ) from information geometry: on$${\text {Dens}}_+(M)$$ Dens + ( M ) , the geodesic equations of$$F_p$$ F p and$$\nabla ^{(\alpha )}$$ ( α ) coincide, for$$p = 2/(1-\alpha )$$ p = 2 / ( 1 - α ) . Both are pullbacks of canonical constructions on$$L^p(M)$$ L p ( M ) , in which geodesics are simply straight lines. In particular, this gives a new variational interpretation of$$\alpha $$ α -geodesics as being energy minimizing curves. On$${\text {Prob}}(M)$$ Prob ( M ) , the$$F_p$$ F p and$$\nabla ^{(\alpha )}$$ ( α ) geodesics can still be thought as pullbacks of natural operations on the unit sphere in$$L^p(M)$$ L p ( M ) , but in this case they no longer coincide unless$$p=2$$ p = 2 . Using this transformation, we solve the geodesic equation of the$$\alpha $$ α -connection by showing that the geodesic are pullbacks of projections of straight lines onto the unit sphere, and they always cease to exists after finite time when they leave the positive part of the sphere. This unveils the geometric structure of solutions to the generalized Proudman–Johnson equations, and generalizes them to higher dimensions. In addition, we calculate the associate tensors of$$F_p$$ F p , and study their relation to$$\nabla ^{(\alpha )}$$ ( α )
    more » « less
  3. Abstract We obtain new$$L_p$$ L p estimates for subsolutions to fully nonlinear equations. Based on our$$L_p$$ L p estimates, we further study several topics such as the third and fourth order derivative estimates for concave fully nonlinear equations, critical exponents of$$L_p$$ L p estimates and maximum principles, and the existence and uniqueness of solutions to fully nonlinear equations on the torus with free terms in the$$L_p$$ L p spaces or in the space of Radon measures. 
    more » « less
  4. Abstract We obtain new optimal estimates for the$$L^{2}(M)\to L^{q}(M)$$ L 2 ( M ) L q ( M ) ,$$q\in (2,q_{c}]$$ q ( 2 , q c ] ,$$q_{c}=2(n+1)/(n-1)$$ q c = 2 ( n + 1 ) / ( n 1 ) , operator norms of spectral projection operators associated with spectral windows$$[\lambda ,\lambda +\delta (\lambda )]$$ [ λ , λ + δ ( λ ) ] , with$$\delta (\lambda )=O((\log \lambda )^{-1})$$ δ ( λ ) = O ( ( log λ ) 1 ) on compact Riemannian manifolds$$(M,g)$$ ( M , g ) of dimension$$n\ge 2$$ n 2 all of whose sectional curvatures are nonpositive or negative. We show that these two different types of estimates are saturated on flat manifolds or manifolds all of whose sectional curvatures are negative. This allows us to classify compact space forms in terms of the size of$$L^{q}$$ L q -norms of quasimodes for each Lebesgue exponent$$q\in (2,q_{c}]$$ q ( 2 , q c ] , even though it is impossible to distinguish between ones of negative or zero curvature sectional curvature for any$$q>q_{c}$$ q > q c
    more » « less
  5. Abstract We prove that the solutions to the discrete nonlinear Schrödinger equation with non-local algebraically decaying coupling converge strongly in$$L^2({\mathbb {R}}^2)$$ L 2 ( R 2 ) to those of the continuum fractional nonlinear Schrödinger equation, as the discretization parameter tends to zero. The proof relies on sharp dispersive estimates that yield the Strichartz estimates that are uniform in the discretization parameter. An explicit computation of the leading term of the oscillatory integral asymptotics is used to show that the best constants of a family of dispersive estimates blow up as the non-locality parameter$$\alpha \in (1,2)$$ α ( 1 , 2 ) approaches the boundaries. 
    more » « less