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

来源：

ADVANCES IN APPLIED PROBABILITY | 2012年 / 44卷 / 04期

基金：

美国国家科学基金会;

关键词：

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 [J].

Arora, S ;

Hazan, E ;

Kale, S .

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 [J].

Avin, Chen ;

Ercal, Gunes .

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 [J].

Belkin, Mikhail ;

Niyogi, Partha .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (08) :1289-1308

[9] Exact rates in density support estimation [J].

Biau, Gerard ;

Cadre, Benoit ;

Pelletier, Bruno .

JOURNAL OF MULTIVARIATE ANALYSIS, 2008, 99 (10) :2185-2207

[10]

Boyd Stephen P, 2005, P SIAM ANALCO, P240

← 1 2 3 4 5 →