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 length 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.

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

\emptyset =K_{0}\subseteq K_{1}\subseteq \ldots \subseteq K_{n}=K

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

A persistence module over a partially ordered set $P$ is a set of vector spaces $U_{t}$ indexed by $P$ , with a linear map $u_t^s: U_s \to U_t$ whenever $s\leq t$ , with $u_{t}^{t}$ equal to the identity and $u_{t}^{s}\circ u_{s}^{r}=u_{t}^{r}$ for $r \leq s \leq t$ . Equivalently, we may consider it as a functor from $P$ considered as a category to the category of vector spaces (or $R$ -modules). There is a classification of persistence modules over a field $F$ indexed by $\mathbb {N}$ :

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 $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 $t_{i}$ and never disappear, while the torsion parts correspond to those that appear at filtration level $r_j$ and last for $s_{j}$ steps of the filtration (or equivalently, disappear at filtration level $s_j+r_j$ ).^[4]

This theorem 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.

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

Software package	Creator	Latest release	Release date	Software license^[5]	Open source	Programming language
javaPlex	Andrew Tausz, Mikael Vejdemo-Johansson, Henry Adams	4.2.5	000000002016-03-14-000014 March 2016	Custom	Yes	Java, Matlab
Dionysus	Dmitriy Morozov			GPL	Yes	C++, Python bindings
Perseus	Vidit Nanda	4.0 beta		GPL	Yes	C++
PHAT	Ulrich Bauer, Michael Kerber, Jan Reininghaus	1.4.1			Yes	C++
DIPHA	Jan Reininghaus				Yes	C++
Gudhi	INRIA	1.3.0	000000002016-04-15-000015 April 2016		Yes	C++
CTL	Ryan Lewis	0.2			Yes	C++
phom
TDA	Brittany T. Fasy, Jisu Kim, Fabrizio Lecci, Clement Maria, Vincent Rouvreau	1.5	000000002016-06-16-000016 June 2016			R
Ripser	Ulrich Bauer	1.0.1	15 September 2016	LGPL	Yes	C++
Software package	Creator	Latest stable release	Stable release date	Software license^[5]	Open source	Programming language

References

↑ Carlsson, Gunnar (2009). "Topology and data". AMS Bulletin 46(2), 255–308.
↑ Edelsbrunner, H and Harer, J (2010). Computational Topology: An Introduction. American Mathematical Society.
↑ Verri, A, Uras, C, Frosini, P and Ferri, M (1993). On the use of size functions for shape analysis, Biological Cybernetics, 70, 99–107.
↑ 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.
1 2 Licenses here are a summary, and are not taken to be complete statements of the licenses. Some packages may use libraries under different licenses.

This article is issued from Wikipedia - version of the 11/24/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Persistent homology

See also

References