THE NORMALIZED GRAPH CUT AND CHEEGER CONSTANT: FROM DISCRETE TO CONTINUOUS

被引:22
作者
Arias-Castro, Ery [1 ]
Pelletier, Bruno [2 ]
Pudlo, Pierre [3 ]
机构
[1] Univ Calif San Diego, Dept Math, San Diego, CA 92103 USA
[2] Univ Rennes 2, CNRS, IRMAR, Dept Math,UMR 6625, F-35043 Rennes, France
[3] Univ Montpellier 2, CNRS, Dept Math, I3M,UMR 5149, F-34095 Montpellier 5, France
基金
美国国家科学基金会;
关键词
Cheeger isoperimetric constant of a manifold; conductance of a graph; neighborhood graph; spectral clustering; U-process; empirical process; CONVERGENCE; LAPLACIAN;
D O I
10.1239/aap/1354716583
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
Let M be a bounded domain of R-d with a 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.
引用
收藏
页码:907 / 937
页数:31
相关论文
共 44 条
  • [1] [Anonymous], 1970, Problems in Analysis
  • [2] [Anonymous], 1999, TOPOLOGY P
  • [3] [Anonymous], 1994, Graduate Texts in Mathematics
  • [4] [Anonymous], 1999, DECOUPLING
  • [5] O(√log n) approximation to SPARSEST CUT in (O)over-tilde(n2) time
    Arora, S
    Hazan, E
    Kale, S
    [J]. 45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, : 238 - 247
  • [6] On the cover time and mixing time of random geometric graphs
    Avin, Chen
    Ercal, Gunes
    [J]. THEORETICAL COMPUTER SCIENCE, 2007, 380 (1-2) : 2 - 22
  • [7] Belkin M, 2002, ADV NEUR IN, V14, P585
  • [8] Towards a theoretical foundation for Laplacian-based manifold methods
    Belkin, Mikhail
    Niyogi, Partha
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (08) : 1289 - 1308
  • [9] Exact rates in density support estimation
    Biau, Gerard
    Cadre, Benoit
    Pelletier, Bruno
    [J]. JOURNAL OF MULTIVARIATE ANALYSIS, 2008, 99 (10) : 2185 - 2207
  • [10] Boyd Stephen P, 2005, P SIAM ANALCO, P240