# Persistent homology

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.[1]

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.[2] A similar construction uses a nested sequence of Vietoris–Rips complexes known as the Vietoris–Rips filtration.[3]

## 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.[4] Persistent Betti numbers for ${\displaystyle p=0}$ coincide with the size function, a predecessor of persistent homology.[5]

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}}}$.[6]

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[x]\oplus \left(\bigoplus _{j}x^{r_{j}}\cdot (F[x]/(x^{s_{j}}\cdot F[x]))\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}}$).[7] [6]

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,[6] 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 }}$. [8]

## Computation

There are various software packages for computing persistence intervals of a finite filtration.[9] The principal algorithm is based on the bringing of the filtered complex to its canonical form by upper-triangular matrices.[6]

Software package Creator Latest release Release date Software license[10] Open source Programming language Features
OpenPH Rodrigo Mendoza-Smith, Jared Tanner 0.0.1 25 April 2019 Apache 2.0 Yes Matlab, CUDA GPU acceleration
javaPlex Andrew Tausz, Mikael Vejdemo-Johansson, Henry Adams 4.2.5 14 March 2016 Custom Yes Java, Matlab
Dionysus Dmitriy Morozov 2.0.8 24 November 2020 Modified BSD Yes C++, Python bindings
Perseus Vidit Nanda 4.0 beta GPL Yes C++
PHAT [11] Ulrich Bauer, Michael Kerber, Jan Reininghaus 1.4.1 Yes C++
DIPHA Jan Reininghaus Yes C++
Gudhi [12] INRIA 3.4.0 15 December 2020 MIT/GPLv3 Yes C++, Python bindings
CTL Ryan Lewis 0.2 BSD Yes C++
phom Andrew Tausz Yes R
TDA Brittany T. Fasy, Jisu Kim, Fabrizio Lecci, Clement Maria, Vincent Rouvreau 1.5 16 June 2016 Yes R Provides R interface for GUDHI, Dionysus and PHAT
Eirene Gregory Henselman 1.0.1 9 March 2019 GPLv3 Yes Julia
Ripser Ulrich Bauer 1.0.1 15 September 2016 MIT Yes C++
the Topology ToolKit Julien Tierny, Guillaume Favelier, Joshua Levine, Charles Gueunet, Michael Michaux 0.9.8 29 July 2019 BSD Yes C++, VTK and Python bindings
libstick Stefan Huber 0.2 27 November 2014 MIT Yes C++
Ripser++ Simon Zhang, Mengbai Xiao, and Hao Wang 1.0 March 2020 MIT Yes CUDA, C++, Python bindings GPU acceleration

## 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. ^ a b c d 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. ^ 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.
10. ^ Licenses here are a summary, and are not taken to be complete statements of the licenses. Some packages may use libraries under different licenses.
11. ^ 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.
12. ^ 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.