Persistent homology

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]

See homology for an introduction to the notation.

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.

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

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

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}}$).[5] [4]

Each of these two theorems allows us to uniquely represent the persistent homology of a filtered simplicial complex with a 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,[4] 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. There 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 },}$$

called the bottleneck distance. 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 }}$. [6]

Computation

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

Software package	Creator	Latest release	Release date	Software license[8]	Open source	Programming language	Features
OpenPH	Rodrigo Mendoza-Smith, Jared Tanner	0.0.1	25 April 2019	Apache 2.0	Yes	Matlab, CUDA
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 [9]	Ulrich Bauer, Michael Kerber, Jan Reininghaus	1.4.1			Yes	C++
DIPHA	Jan Reininghaus				Yes	C++
Gudhi [10]	INRIA	3.0.0	23 September 2019	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
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

See also

• Topological data analysis
• Computational topology

References

1. Carlsson, Gunnar (2009). "Topology and data". AMS Bulletin 46(2), 255–308.
2. Edelsbrunner, H and Harer, J (2010). Computational Topology: An Introduction. American Mathematical Society.
3. Verri, A, Uras, C, Frosini, P and Ferri, M (1993). On the use of size functions for shape analysis, Biological Cybernetics, 70, 99–107.
4. Barannikov, Sergey (1994). "Framed Morse complex and its invariants". Advances in Soviet Mathematics. 21: 93–115.
5. 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.
6. 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.
7. Otter, Nina; Porter, Mason A; Tillmann, Ulrike; et al. (2017-08-09). "A roadmap for the computation of persistent homology". EPJ Data Science. Springer. 6 (1): 17. doi:10.1140/epjds/s13688-017-0109-5. ISSN 2193-1127.
8. Licenses here are a summary, and are not taken to be complete statements of the licenses. Some packages may use libraries under different licenses.
9. 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.
10. Maria, Clément; Boissonnat, Jean-Daniel; Glisse, Marc; et al. (2014). "The Gudhi Library: Simplicial Complexes and Persistent Homology". Mathematical Software – ICMS 2014. Berlin, Heidelberg: Springer. pp. 167–174. doi:10.1007/978-3-662-44199-2_28. ISBN 978-3-662-44198-5. ISSN 0302-9743.