Misplaced Pages

See homology for an introduction to the notation.

Persistent homology is a method for computing topological features of a space at different spatial resolutions. More persistent features are detected over a wide range of spatial scales and are deemed more likely to represent true features of the underlying space rather than artifacts of sampling, noise, or particular choice of parameters.

To find the persistent homology of a space, the space must first be represented as a simplicial complex. A distance function on the underlying space corresponds to a filtration of the simplicial complex, that is a nested sequence of increasing subsets. One common method of doing this is via taking the sublevel filtration of the distance to a point cloud, or equivalently, the offset filtration on the point cloud and taking its nerve in order to get the simplicial filtration known as Čech filtration. A similar construction uses a nested sequence of Vietoris–Rips complexes known as the Vietoris–Rips filtration.

Definition

Formally, consider a real-valued function on a simplicial complex ${\displaystyle f:K\rightarrow \mathbb {R} }$ that is non-decreasing on increasing sequences of faces, so ${\displaystyle f(\sigma )\leq f(\tau )}$ whenever ${\displaystyle \sigma }$ is a face of ${\displaystyle \tau }$ in ${\displaystyle K}$. Then for every ${\displaystyle a\in \mathbb {R} }$ the sublevel set ${\displaystyle K_{a}=f^{-1}((-\infty ,a])}$ is a subcomplex of K, and the ordering of the values of ${\displaystyle f}$ on the simplices in ${\displaystyle K}$ (which is in practice always finite) induces an ordering on the sublevel complexes that defines a filtration

${\displaystyle \emptyset =K_{0}\subseteq K_{1}\subseteq \cdots \subseteq K_{n}=K}$

When ${\displaystyle 0\leq i\leq j\leq n}$, the inclusion ${\displaystyle K_{i}\hookrightarrow K_{j}}$ induces a homomorphism ${\displaystyle f_{p}^{i,j}:H_{p}(K_{i})\rightarrow H_{p}(K_{j})}$ on the simplicial homology groups for each dimension ${\displaystyle p}$. The ${\displaystyle p^{\text{th}}}$ persistent homology groups are the images of these homomorphisms, and the ${\displaystyle p^{\text{th}}}$ persistent Betti numbers ${\displaystyle \beta _{p}^{i,j}}$ are the ranks of those groups. Persistent Betti numbers for ${\displaystyle p=0}$ coincide with the size function, a predecessor of persistent homology.

Any filtered complex over a field ${\displaystyle F}$ can be brought by a linear transformation preserving the filtration to so called canonical form, a canonically defined direct sum of filtered complexes of two types: one-dimensional complexes with trivial differential ${\displaystyle d(e_{t_{i}})=0}$ and two-dimensional complexes with trivial homology ${\displaystyle d(e_{s_{j}+r_{j}})=e_{r_{j}}}$.

A persistence module over a partially ordered set ${\displaystyle P}$ is a set of vector spaces ${\displaystyle U_{t}}$ indexed by ${\displaystyle P}$, with a linear map ${\displaystyle u_{t}^{s}:U_{s}\to U_{t}}$ whenever ${\displaystyle s\leq t}$, with ${\displaystyle u_{t}^{t}}$ equal to the identity and ${\displaystyle u_{t}^{s}\circ u_{s}^{r}=u_{t}^{r}}$ for ${\displaystyle r\leq s\leq t}$. Equivalently, we may consider it as a functor from ${\displaystyle P}$ considered as a category to the category of vector spaces (or ${\displaystyle R}$-modules). There is a classification of persistence modules over a field ${\displaystyle F}$ indexed by ${\displaystyle \mathbb {N} }$: $${\displaystyle U\simeq \bigoplus _{i}x^{t_{i}}\cdot F\oplus \left(\bigoplus _{j}x^{r_{j}}\cdot (F/(x^{s_{j}}\cdot F))\right).}$$ Multiplication by ${\displaystyle x}$ corresponds to moving forward one step in the persistence module. Intuitively, the free parts on the right side correspond to the homology generators that appear at filtration level ${\displaystyle t_{i}}$ and never disappear, while the torsion parts correspond to those that appear at filtration level ${\displaystyle r_{j}}$ and last for ${\displaystyle s_{j}}$ steps of the filtration (or equivalently, disappear at filtration level ${\displaystyle s_{j}+r_{j}}$).

Each of these two theorems allows us to uniquely represent the persistent homology of a filtered simplicial complex with a persistence barcode or persistence diagram. A barcode represents each persistent generator with a horizontal line beginning at the first filtration level where it appears, and ending at the filtration level where it disappears, while a persistence diagram plots a point for each generator with its x-coordinate the birth time and its y-coordinate the death time. Equivalently the same data is represented by Barannikov's canonical form, where each generator is represented by a segment connecting the birth and the death values plotted on separate lines for each ${\displaystyle p}$.

Stability

Persistent homology is stable in a precise sense, which provides robustness against noise. The bottleneck distance is a natural metric on the space of persistence diagrams given by $${\displaystyle W_{\infty }(X,Y):=\inf _{\varphi :X\to Y}\sup _{x\in X}\Vert x-\varphi (x)\Vert _{\infty },}$$ where ${\displaystyle \varphi }$ ranges over bijections. A small perturbation in the input filtration leads to a small perturbation of its persistence diagram in the bottleneck distance. For concreteness, consider a filtration on a space ${\displaystyle X}$ homeomorphic to a simplicial complex determined by the sublevel sets of a continuous tame function ${\displaystyle f:X\to \mathbb {R} }$. The map ${\displaystyle D}$ taking ${\displaystyle f}$ to the persistence diagram of its ${\displaystyle k}$th homology is 1-Lipschitz with respect to the ${\displaystyle \sup }$-metric on functions and the bottleneck distance on persistence diagrams. That is, ${\displaystyle W_{\infty }(D(f),D(g))\leq \lVert f-g\rVert _{\infty }}$.

Computation

The principal algorithm is based on the bringing of the filtered complex to its canonical form by upper-triangular matrices and runs in worst-case cubical complexity in the number of simplices. The fastest known algorithm for computing persistent homology runs in matrix multiplication time.

Since the number of simplices is highly relevant for computation time, finding filtered simplicial simplicial complexes with few simplexes is an active research area. Several approaches have been proposed to reduce the number of simplices in a filtered simplicial complex in order to approximate persistent homology.

Generalization

Topological Laplacians, such as Hodge Laplacians on differentiable manifolds, combinatorial Laplacians for point clouds, and Khovanov Laplacians for knots and links, extract topological information specific to their respective data domains. Despite being defined in different contexts, these topological Laplacians share a common algebraic structure. Specifically, they are constructed using the (co-)boundary operator and its adjoint. The kernels of these Laplacians are isomorphic to homology groups, meaning the number of zero eigenvalues corresponds to the Betti numbers of the associated homology groups. Furthermore, the nonzero eigenvalues provide additional insights into the data, particularly from the perspective of spectral theory.

Hodge Laplacians, combinatorial Laplacians, and Khovanov Laplacians leverage mathematical tools from differential geometry, graph theory, and geometric topology, respectively, to generalize the classical theory of homology in algebraic topology. Each serves as a bridge between algebraic topology and its specific mathematical field.

Persistent Hodge Laplacians were first introduced in 2019 to analyze data on differentiable manifolds. Similarly, persistent combinatorial Laplacians, also referred to as persistent Laplacians, were developed for point cloud data. These frameworks extend classical persistent homology and have sparked significant interest, driving advancements in both theoretical research and practical applications.

Software

There are various software packages for computing persistence intervals of a finite filtration.

See also

• Topological data analysis
• Computational topology

References

1. Carlsson, Gunnar (2009). "Topology and data". AMS Bulletin 46(2), 255–308.
2. Kerber, Michael; Sharathkumar, R. (2013). "Approximate Čech Complex in Low and High Dimensions". In Cai, Leizhen; Cheng, Siu-Wing; Lam, Tak-Wah (eds.). Algorithms and Computation. Lecture Notes in Computer Science. Vol. 8283. Berlin, Heidelberg: Springer. pp. 666–676. doi:10.1007/978-3-642-45030-3_62. ISBN 978-3-642-45030-3. S2CID 5770506.
3. Dey, Tamal K.; Shi, Dayu; Wang, Yusu (2019-01-30). "SimBa: An Efficient Tool for Approximating Rips-filtration Persistence via Simplicial Batch Collapse". ACM Journal of Experimental Algorithmics. 24: 1.5:1–1.5:16. doi:10.1145/3284360. ISSN 1084-6654. S2CID 216028146.
4. Edelsbrunner, H and Harer, J (2010). Computational Topology: An Introduction. American Mathematical Society.
5. Verri, A.; Uras, C.; Frosini, P.; Ferri, M. (1993). "On the use of size functions for shape analysis". Biological Cybernetics. 70 (2): 99–107. doi:10.1007/BF00200823. S2CID 39065932.
6. ^ Barannikov, Sergey (1994). "Framed Morse complex and its invariants". Advances in Soviet Mathematics. 21: 93–115.
7. Zomorodian, Afra; Carlsson, Gunnar (2004-11-19). "Computing Persistent Homology". Discrete & Computational Geometry. 33 (2): 249–274. doi:10.1007/s00454-004-1146-y. ISSN 0179-5376.
8. Cohen-Steiner, David; Edelsbrunner, Herbert; Harer, John (2006-12-12). "Stability of Persistence Diagrams". Discrete & Computational Geometry. 37 (1): 103–120. doi:10.1007/s00454-006-1276-5. ISSN 0179-5376.
9. Morozov, Dmitriy; Skraba, Primoz (2024). "Persistent (Co)Homology in Matrix Multiplication Time". Arxiv. arXiv:2412.02591.
10. Sheehy, Donald R. (June 2013). "Linear-Size Approximations to the Vietoris–Rips Filtration". Discrete & Computational Geometry. 49 (4): 778–796. arXiv:1203.6786. doi:10.1007/s00454-013-9513-1.
11. Botnan, Magnus Bakke; Spreemann, Gard (March 2015). "Approximating persistent homology in Euclidean space through collapses". Applicable Algebra in Engineering, Communication and Computing. 26 (1–2): 73–101. arXiv:1403.0533. doi:10.1007/s00200-014-0247-y.
12. Choudhary, Aruni; Kerber, Michael; Raghvendra, Sharath (2017). "Improved Approximate Rips Filtrations with Shifted Integer Lattices". LIPIcs, Volume 87, ESA 2017. 87: 28:1–28:13. doi:10.4230/LIPIcs.ESA.2017.28.
13. Brun, Morten; Blaser, Nello (June 2019). "Sparse Dowker nerves". Journal of Applied and Computational Topology. 3 (1–2): 1–28. arXiv:1802.03655. doi:10.1007/s41468-019-00028-9.
14. Chanillo, Sagun; Treves, Francois (1997). "On the lowest eigenvalue of the Hodge Laplacian". Journal of Differential Geometry. 45 (2): 273--287.{{cite journal}}: CS1 maint: date and year (link)
15. Eckmann, Beno (1944). "Harmonische funktionen und randwertaufgaben in einem komplex". Commentarii Mathematici Helvetici. 17 (1): 240--255.{{cite journal}}: CS1 maint: date and year (link)
16. Jones, Benjamin; Wei, Guo-Wei (2024). "Khovanov Laplacian and Khovanov Dirac for Knots and Links". ArXiv. arXiv:2411.18841. doi:10.48550/arXiv.:2411.18841.{{cite journal}}: CS1 maint: date and year (link)
17. Chen, Jiahui; Zhao, Rundong; Tong, Yiying; Wei, Guo-Wei (2021). "Evolutionary de Rham-Hodge method". Discrete and Continuous Dynamical Systems. Series B. 26 (7): 3785–38215. arXiv:1912.12388. doi:10.3934/dcdsb.2020257.{{cite journal}}: CS1 maint: date and year (link)
18. Wang, Rui; Nguyen, Duc; Wei, Guo-Wei (2020). "Persistent spectral graph". International Journal for Numerical Methods in Biomedical Engineering. 36 (9): e3376. arXiv:1912.04135. doi:10.1002/cnm.3376.{{cite journal}}: CS1 maint: date and year (link)
19. Mémoli, Facundo; Wan, Zhengchao; Wang, Yusu (2022). "Persistent Laplacians: Properties, Algorithms and Implications". SIAM Journal on Mathematics of Data Science. 4 (2): 858--884. arXiv:2012.02808. doi:10.1137/21M1435471.{{cite journal}}: CS1 maint: date and year (link)
20. Liu, Jian; Li, Jingyan; Wu, Jie (2023). "The algebraic stability for persistent Laplacians". ArXiv: 858--884. arXiv:2302.03902. doi:10.48550/arXiv.2302.03902.{{cite journal}}: CS1 maint: date and year (link)
21. Qiu, Yuchi; Wei, Guo-Wei (2023). "Persistent spectral theory-guided protein engineering". Nature Computational Science. 3 (2): 149–163. doi:10.1038/s43588-022-00394-y. PMC 10456983. PMID 37637776.{{cite journal}}: CS1 maint: date and year (link)
22. Chen, Jiahui; Qiu, Yuchi; Wang, Rui; Wei, Guo-Wei (2022). "Persistent Laplacian projected Omicron BA. 4 and BA. 5 to become new dominating variants". Computers in Biology and Medicine. 151: 106262. arXiv:2205.00532. doi:10.1016/j.compbiomed.2022.106262. PMID 36379191.{{cite journal}}: CS1 maint: date and year (link)
23. Zhenyu, Meng; Kelin, Xia (2021). "Persistent spectral–based machine learning (PerSpect ML) for protein-ligand binding affinity prediction". Science Advances. 7 (19): eabc5329. doi:10.1126/sciadv.abc5329. hdl:10356/151043.{{cite journal}}: CS1 maint: date and year (link)
24. Otter, Nina; Porter, Mason A; Tillmann, Ulrike; et al. (2017-08-09). "A roadmap for the computation of persistent homology". EPJ Data Science. 6 (1). Springer: 17. doi:10.1140/epjds/s13688-017-0109-5. ISSN 2193-1127. PMC 6979512. PMID 32025466.
25. Licenses here are a summary, and are not taken to be complete statements of the licenses. Some packages may use libraries under different licenses.
26. Bauer, Ulrich; Kerber, Michael; Reininghaus, Jan; Wagner, Hubert (2014). "PHAT – Persistent Homology Algorithms Toolbox". Mathematical Software – ICMS 2014. Springer Berlin Heidelberg. pp. 137–143. doi:10.1007/978-3-662-44199-2_24. ISBN 978-3-662-44198-5. ISSN 0302-9743.
27. Maria, Clément; Boissonnat, Jean-Daniel; Glisse, Marc; et al. (2014). "The Gudhi Library: Simplicial Complexes and Persistent Homology". Mathematical Software – ICMS 2014 (PDF). Berlin, Heidelberg: Springer. pp. 167–174. doi:10.1007/978-3-662-44199-2_28. ISBN 978-3-662-44198-5. ISSN 0302-9743. S2CID 17810678.

• Homology theory
• Computational topology