The decomposition of the higher-order homology embedding constructed from the k-Laplacian
The decomposition of the higher-order homology embedding constructed from the k-Laplacian
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Yu-Chia Chen;M. Meilă
中科院分区：
文献类型：
--
作者：
Yu-Chia Chen;M. Meilă
$ k $ -th订单laplacian $ \ mathbf {\ mathcal l} _k $的零空间，称为{\ em $ k $ - th同源矢量}网络。因此，了解同源性嵌入的结构可以从数据中披露几何或拓扑信息。图laplacian $ \ mathbf {\ Mathcal L} _0 $的无效空间嵌入的研究刺激了新的研究和应用，例如具有随机块模型的理论保证和估计器的光谱聚类算法。在这项工作中，我们研究了$ k $ Th同源性嵌入的几何形状，并专注于让人联想到光谱聚类的病例。也就是说，我们将流形的{\ em连接总和}分析为对其同源性嵌入的直接总和的扰动。我们提出了一种算法，以将嵌入与歧管最简单拓扑成分相对应的子空间分解为同源性。提出的框架应用于{\ em最短的同源环检测}问题，这个问题通常是NP-HARD。我们的频谱环检测算法比现有方法更好，并且对诸如点云和图像之类的不同数据有效。
The null space of the $k$-th order Laplacian $\mathbf{\mathcal L}_k$, known as the {\em $k$-th homology vector space}, encodes the non-trivial topology of a manifold or a network. Understanding the structure of the homology embedding can thus disclose geometric or topological information from the data. The study of the null space embedding of the graph Laplacian $\mathbf{\mathcal L}_0$ has spurred new research and applications, such as spectral clustering algorithms with theoretical guarantees and estimators of the Stochastic Block Model. In this work, we investigate the geometry of the $k$-th homology embedding and focus on cases reminiscent of spectral clustering. Namely, we analyze the {\em connected sum} of manifolds as a perturbation to the direct sum of their homology embeddings. We propose an algorithm to factorize the homology embedding into subspaces corresponding to a manifold's simplest topological components. The proposed framework is applied to the {\em shortest homologous loop detection} problem, a problem known to be NP-hard in general. Our spectral loop detection algorithm scales better than existing methods and is effective on diverse data such as point clouds and images.