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} }$:

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

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

See also

• Topological data analysis
• Computational topology

References