Geometric structure of graph Laplacian embeddings
Geometric structure of graph Laplacian embeddings
复制标题
DOI：
--
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
N. G. Trillos;F. Hoffmann;Bamdad Hosseini
中科院分区：
文献类型：
--
作者：
N. G. Trillos;F. Hoffmann;Bamdad Hosseini
我们分析了谱聚类过程中识别粗结构的数据集x_n，.，x_n，特别是研究的几何图形拉普拉斯嵌入形成的基础上，谱聚类算法。更准确地说，我们假设数据是从嵌入在R^d中的流形M上支持的混合模型中采样的，并选取连通性长度尺度e>0来构造核化图拉普拉斯算子。我们引入了一个良好分离的混合模型，它只依赖于模型本身的概念，并证明了当模型是很好的分离，以高概率的嵌入数据集集中在锥是围绕正交向量为中心。我们的结果是有意义的制度，其中e=e（n）被允许衰减到零，在一个足够慢的速度作为数据点的数量增长。该速率取决于支持数据的流形的固有维数。
We analyze the spectral clustering procedure for identifying coarse structure in a data set x₁,…,x_n, and in particular study the geometry of graph Laplacian embeddings which form the basis for spectral clustering algorithms. More precisely, we assume that the data is sampled from a mixture model supported on a manifold M embedded in R^d, and pick a connectivity length-scale e>0 to construct a kernelized graph Laplacian. We introduce a notion of a well-separated mixture model which only depends on the model itself, and prove that when the model is well separated, with high probability the embedded data set concentrates on cones that are centered around orthogonal vectors. Our results are meaningful in the regime where e=e(n) is allowed to decay to zero at a slow enough rate as the number of data points grows. This rate depends on the intrinsic dimension of the manifold on which the data is supported.