Timezone: »
Oral
The decomposition of the higher-order homology embedding constructed from the $k$-Laplacian
Yu-Chia Chen · Marina Meila
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.
Author Information
Yu-Chia Chen (Facebook, Inc.)
Marina Meila (University of Washington)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: The decomposition of the higher-order homology embedding constructed from the $k$-Laplacian »
Tue. Dec 7th 04:30 -- 06:00 PM Room Virtual
More from the Same Authors
-
2019 Poster: Selecting the independent coordinates of manifolds with large aspect ratios »
Yu-Chia Chen · Marina Meila -
2017 Workshop: Synergies in Geometric Data Analysis (TWO DAYS) »
Marina Meila · Frederic Chazal · Yu-Chia Chen