The normalized graph cut and Cheeger constant: from discrete to continuous
From MaRDI portal
Publication:4906501
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 410743 (Why is no real title available?)
- scientific article; zbMATH DE number 3868094 (Why is no real title available?)
- scientific article; zbMATH DE number 1978331 (Why is no real title available?)
- scientific article; zbMATH DE number 3215519 (Why is no real title available?)
- scientific article; zbMATH DE number 3337135 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A graph-based estimator of the number of clusters
- A nonparametric approach to the estimation of lengths and surface areas
- A note on the isoperimetric constant
- Computing persistent homology
- Consistency of spectral clustering
- Curvature Measures
- Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
- Exact rates in density support estimation
- Finding the homology of submanifolds with high confidence from random samples
- From graph to manifold Laplacian: the convergence rate
- Granulometric smoothing
- Local empirical processes near boundaries of convex bodies
- On the Volume of Tubes
- On the area and perimeter of a random convex hull in a bounded convex set
- On the cover time and mixing time of random geometric graphs
- Operator norm convergence of spectral clustering on level sets
- Probability Inequalities for Sums of Bounded Random Variables
- Random Geometric Graphs
- Some remarks on uniqueness and regularity of Cheeger sets
- Spectral partitioning works: planar graphs and finite element meshes
- The theory of multidimensional persistence
- Topology and data
- Towards a theoretical foundation for Laplacian-based manifold methods
- Variation and optimization of formes. A geometric analysis
- Weak feature size and persistent homology: computing homology of solids in \(\mathbb{R}^n\) from noisy data samples
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
Cited in
(15)- Continuum limit of total variation on point clouds
- A Cheeger cut for uniform hypergraphs
- scientific article; zbMATH DE number 5499335 (Why is no real title available?)
- 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
- Variational limits of \(k\)-NN graph-based functionals 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
- Cheeger inequalities for unbounded graph Laplacians
- Optimal Cheeger cuts and bisections of random geometric graphs
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)
