标题： 通过单纯形路径的鲁棒多流形聚类 显示英文标题

标题： Robust Multi-Manifold Clustering via Simplex Paths

摘要： 本文介绍了一种新颖的几何方法用于多流形聚类（MMC），即对一组可能相交的d维流形进行聚类，以分离出各个流形组件。我们首先在d-单形上计算一个局部图，使用相邻单形之间的二面角作为图权重，然后在此单形图中计算无限路径距离。此过程给出了一个单形上的度量，我们称之为最大角路径距离（LAPD）。我们分析了在随机采样下LAPD的性质，并证明通过适当的去噪过程，该度量可以以高概率分离流形组件。我们在合成和真实世界数据集上进行了大量数值实验，验证了所提出的方法。这些实验表明，该方法对噪声、曲率和小的相交角度具有鲁棒性，并且通常优于其他MMC算法。此外，我们提供了一个高度可扩展的所提出算法的实现，该实现利用了无限路径距离的近似方案，以实现准线性计算复杂度。 显示英文摘要

摘要： This article introduces a novel, geometric approach for multi-manifold clustering (MMC), i.e. for clustering a collection of potentially intersecting, d-dimensional manifolds into the individual manifold components. We first compute a locality graph on d-simplices, using the dihedral angle in between adjacent simplices as the graph weights, and then compute infinity path distances in this simplex graph. This procedure gives a metric on simplices which we refer to as the largest angle path distance (LAPD). We analyze the properties of LAPD under random sampling, and prove that with an appropriate denoising procedure, this metric separates the manifold components with high probability. We validate the proposed methodology with extensive numerical experiments on both synthetic and real-world data sets. These experiments demonstrate that the method is robust to noise, curvature, and small intersection angle, and generally out-performs other MMC algorithms. In addition, we provide a highly scalable implementation of the proposed algorithm, which leverages approximation schemes for infinity path distance to achieve quasi-linear computational complexity.