Large sample spectral analysis of graph-based multi-manifold clustering
Large sample spectral analysis of graph-based multi-manifold clustering
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
N. G. Trillos;Pengfei He;Chenghui Li
中科院分区：
文献类型：
--
作者：
N. G. Trillos;Pengfei He;Chenghui Li
在这项工作中，我们研究了基于图的多流形聚类算法的统计性质。在MMC中，目标是检索在给定欧几里得数据集下的多流形结构，当假设该多流形结构是通过对流形的并集上的分布进行采样而获得的时，该流形可以彼此相交并且可以具有不同的维度。我们研究了数据集上的相似图必须满足的充分条件，以使它们对应的图的拉普拉斯算子能够捕捉正确的几何信息来解决MMC问题。准确地说，我们给出了张化拉普拉斯的谱逼近的高概率误差界，该图由观测得到；恢复的张化拉普拉斯包含所有单个基础流形的所有几何信息。我们给出了一族相似图的例子，我们称之为具有角度约束的环形邻近图，满足这些充分条件。我们将我们的图族与文献中基于切平面排列的其他结构进行了比较。大量的数值实验扩展了我们的理论在MMC问题上提供的见解。
In this work we study statistical properties of graph-based algorithms for multi-manifold clustering (MMC). In MMC the goal is to retrieve the multi-manifold structure underlying a given Euclidean data set when this one is assumed to be obtained by sampling a distribution on a union of manifolds $\mathcal{M} = \mathcal{M}_1 \cup\dots \cup \mathcal{M}_N$ that may intersect with each other and that may have different dimensions. We investigate sufficient conditions that similarity graphs on data sets must satisfy in order for their corresponding graph Laplacians to capture the right geometric information to solve the MMC problem. Precisely, we provide high probability error bounds for the spectral approximation of a tensorized Laplacian on $\mathcal{M}$ with a suitable graph Laplacian built from the observations; the recovered tensorized Laplacian contains all geometric information of all the individual underlying manifolds. We provide an example of a family of similarity graphs, which we call annular proximity graphs with angle constraints, satisfying these sufficient conditions. We contrast our family of graphs with other constructions in the literature based on the alignment of tangent planes. Extensive numerical experiments expand the insights that our theory provides on the MMC problem.