21810 articles – 15605 references  [version française]

hal-00473264, version 3

The Normalized Graph Cut and Cheeger Constant: from Discrete to Continuous

Ery Arias-Castro () 1, Bruno Pelletier () 2, Pierre Pudlo () 3

Advances in Applied Probability 44, 4 (2012) 907-937

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.

  • 1:  Department of Mathematics, University of California, San Diego (Math Dept, UCSD)
  • University of California, San Diego
  • 2:  Institut de Recherche Mathématique de Rennes (IRMAR)
  • CNRS : UMR6625 – Université de Rennes 1 – École normale supérieure de Cachan - ENS Cachan – Institut National des Sciences Appliquées (INSA) : - RENNES – Université de Rennes II - Haute Bretagne
  • 3:  Institut de Mathématiques et de Modélisation de Montpellier (I3M)
  • CNRS : UMR5149 – Université Montpellier II - Sciences et techniques
  • Domain : Mathematics/Statistics
    Statistics/Statistics Theory
  • Keywords : Cheeger isoperimetric constant of a manifold – conductance of a graph – neighborhood graph – spectral clustering – U-processes – empirical processes
  • Available versions :  v1 (2010-04-30) v2 (2010-05-31) v3 (2011-06-09)
 
  • hal-00473264, version 3
  • http://hal.archives-ouvertes.fr/hal-00473264
  • oai:hal.archives-ouvertes.fr:hal-00473264
  • From: Pierre Pudlo <>
  • Submitted on: Thursday, 9 June 2011 12:56:52
  • Updated on: Wednesday, 13 March 2013 11:05:49