论文标题
从剪切到等数不平等：cheeger削减数据云的收敛速率
From graph cuts to isoperimetric inequalities: Convergence rates of Cheeger cuts on data clouds
论文作者
论文摘要
在这项工作中，我们研究了依赖于平衡图切割的优化的基于图的聚类算法的统计特性，主要示例是对Cheeger切割的优化。我们考虑从一般平滑紧凑型歧管$ M $上支持的基础分布中采样的数据构建的接近图。在这种情况下，我们获得了脸颊常数和相关的Cheeger切口的高概率收敛速率。关键的技术工具是对插值操作员的仔细估计，这些插值将经验cheger削减到连续体中，以及等速问题的连续性稳定性估计。据我们所知，这里获得的定量估计是其中的第一个。
In this work we study statistical properties of graph-based clustering algorithms that rely on the optimization of balanced graph cuts, the main example being the optimization of Cheeger cuts. We consider proximity graphs built from data sampled from an underlying distribution supported on a generic smooth compact manifold $M$. In this setting, we obtain high probability convergence rates for both the Cheeger constant and the associated Cheeger cuts towards their continuum counterparts. The key technical tools are careful estimates of interpolation operators which lift empirical Cheeger cuts to the continuum, as well as continuum stability estimates for isoperimetric problems. To our knowledge the quantitative estimates obtained here are the first of their kind.
