论文标题
加权cheeger和Buser不平等，应用于聚类和切割概率密度
Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities
论文作者
论文摘要
在本文中，我们显示了概率密度函数的稀疏或等值剪切与其主要特征函数的cheeger剪切有关，以适当地定义“稀疏切割”和“主要特征功能”。 我们在概率密度设置中构建了这些适当的定义，这些定义是稀疏切割和主征函数的定义。然后，我们证明了与Alon-Milman的标准化图Laplacian相似的Cheeger和Buser型不平等现象。我们证明，对于大多数稀疏切割和本金征函数的大多数定义，没有这种不平等。我们将此结果应用于生成新的算法，以切割概率密度和聚类数据，包括光谱聚类的原则变体。
In this paper, we show how sparse or isoperimetric cuts of a probability density function relate to Cheeger cuts of its principal eigenfunction, for appropriate definitions of `sparse cut' and `principal eigenfunction'. We construct these appropriate definitions of sparse cut and principal eigenfunction in the probability density setting. Then, we prove Cheeger and Buser type inequalities similar to those for the normalized graph Laplacian of Alon-Milman. We demonstrate that no such inequalities hold for most prior definitions of sparse cut and principal eigenfunction. We apply this result to generate novel algorithms for cutting probability densities and clustering data, including a principled variant of spectral clustering.
