The normalized graph cut and Cheeger constant: from discrete to continuous
From MaRDI portal
Publication:4906501
DOI10.1239/AAP/1354716583zbMATH Open1318.62105arXiv1004.5485OpenAlexW3098439932MaRDI QIDQ4906501FDOQ4906501
Authors: Ery Arias-Castro, Bruno Pelletier, Pierre Pudlo 
Publication date: 28 February 2013
Published in: Advances in Applied Probability (Search for Journal in Brave)
Abstract: Let M be a bounded domain of a Euclidian space with smooth boundary. We relate the Cheeger constant of M and the conductance of a neighborhood graph defined on a random sample from M. By restricting the minimization defining the latter over a particular class of subsets, we obtain consistency (after normalization) as the sample size increases, and show that any minimizing sequence of subsets has a subsequence converging to a Cheeger set of M.
Full work available at URL: https://arxiv.org/abs/1004.5485
Recommendations
empirical processspectral clusteringneighborhood graph\(U\)-processCheeger isoperimetric constant of a manifoldconductance of a graph
Cites Work
- The theory of multidimensional persistence
- Finding the homology of submanifolds with high confidence from random samples
- Curvature Measures
- Topology and data
- Random Geometric Graphs
- Title not available (Why is that?)
- Towards a theoretical foundation for Laplacian-based manifold methods
- Probability Inequalities for Sums of Bounded Random Variables
- A graph-based estimator of the number of clusters
- Consistency of spectral clustering
- Granulometric smoothing
- Computing persistent homology
- On the Volume of Tubes
- Variation and optimization of formes. A geometric analysis
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- From graph to manifold Laplacian: the convergence rate
- Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
- Some remarks on uniqueness and regularity of Cheeger sets
- A nonparametric approach to the estimation of lengths and surface areas
- Title not available (Why is that?)
- A note on the isoperimetric constant
- Spectral partitioning works: planar graphs and finite element meshes
- Title not available (Why is that?)
- On the cover time and mixing time of random geometric graphs
- Exact rates in density support estimation
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
- Local empirical processes near boundaries of convex bodies
- Weak feature size and persistent homology
- Operator norm convergence of spectral clustering on level sets
- On the area and perimeter of a random convex hull in a bounded convex set
Cited In (15)
- Variational Limits of $k$-NN Graph-Based Functionals on Data Clouds
- Continuum limit of total variation on point clouds
- A Cheeger cut for uniform hypergraphs
- Title not available (Why is that?)
- Consistency of modularity clustering on random geometric graphs
- A variational approach to the consistency of spectral clustering
- Network connectivity assessment and improvement through relay node deployment
- From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
- Theoretical Analysis of Active Contours on Graphs
- Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations
- The coreness and H-index of random geometric graphs
- Estimating perimeter using graph cuts
- Kazdan-Warner equation on infinite graphs
- Optimal Cheeger cuts and bisections of random geometric graphs
- Cheeger inequalities for unbounded graph Laplacians
This page was built for publication: The normalized graph cut and Cheeger constant: from discrete to continuous
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4906501)
