On the Estimation of the Cheeger Constant
summary
Proves that for fixed measurable sets with positive reach the Rn-neighborhood graph cut converges to the continuous perimeter when Rn → 0 slowly, using U-statistics concentration and tubular-neighborhood volume estimates; shows the graph Cheeger value converges to the manifold Cheeger value after restricting to sets with boundary reach ≥ ρn → 0 and controlling bias uniformly; builds a data-dependent minimizer whose subsequences converge in L1 to Cheeger sets via De Giorgi compactness; spectral-clustering consistency remains open.
AI-written summary · about
chapters (10)
- 0:00Introduction to clustering
- 1:31Graph construction methods
- 3:51Defining the Cheeger constant
- 7:00Spectral heuristics
- 9:14Large sample behavior
- 12:08Geometric regularity and reach
- 16:03Formalizing continuous cuts
- 24:13Convergence theorem
- 28:47Proof approach and deviations
- 35:11Estimation and final remarks
related talks
49mGeneralized Cheeger Inequalities and Constrained Clustering
01h 10mPDE on Graphs and Their Continuum Limits
01h 31mGraphons and Graph Limits 2
01h 03mHigh Dimensional Geometry and Concentration II
01h 11m(Hidden) Symmetries of Computational Problems (continued)
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
57mHigh Dimensional Geometry and Concentration I
28mData Driven Convergence in Statistical Estimators