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.
翻译:Laplacian $\mathbf_mathcal L ⁇ k$的空格,称为 $ $k$-th同质矢量空间} 的空格空间, 编码一个元件或网络的非三元表层。 了解同族体嵌入的结构可以由此披露数据中的几何或地貌信息。 对 Laplacian $\ mathbb_mathcal L ⁇ 0$ 的空格进行的研究, 激发了新的研究和应用, 如带理论保障的光谱组合算法和Stochastic Block 模型的估测器。 在这项工作中, 我们调查元元件同族体嵌入的非三元表层结构的几何结构, 并关注重现光谱集的几例。 也就是说, 我们分析元件的 $em 连接总和共性总和共性嵌入的直接和之和。 我们建议一种算法将同系嵌入子空间的分解算法, 与最简单的顶层的顶层图像组件组成者, 将一个最短的框架应用到普通的轨道 。 在一般的解中, 我们所认识的解路路段的解问题。