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 [math]\displaystyle{ f:K \rightarrow \mathbb{R} }[/math] that is non-decreasing on increasing sequences of faces, so [math]\displaystyle{ f(\sigma) \leq f(\tau) }[/math] whenever [math]\displaystyle{ \sigma }[/math] is a face of [math]\displaystyle{ \tau }[/math] in [math]\displaystyle{ K }[/math]. Then for every [math]\displaystyle{ a \in \mathbb{R} }[/math] the sublevel set [math]\displaystyle{ K_a=f^{-1}((-\infty, a]) }[/math] is a subcomplex of K, and the ordering of the values of [math]\displaystyle{ f }[/math] on the simplices in [math]\displaystyle{ K }[/math] (which is in practice always finite) induces an ordering on the sublevel complexes that defines a filtration
- [math]\displaystyle{ \emptyset = K_0 \subseteq K_1 \subseteq \cdots \subseteq K_n = K }[/math]
When [math]\displaystyle{ 0\leq i \leq j \leq n }[/math], the inclusion [math]\displaystyle{ K_i \hookrightarrow K_j }[/math] induces a homomorphism [math]\displaystyle{ f_p^{i,j}:H_p(K_i)\rightarrow H_p(K_j) }[/math] on the simplicial homology groups for each dimension [math]\displaystyle{ p }[/math]. The [math]\displaystyle{ p^\text{th} }[/math] persistent homology groups are the images of these homomorphisms, and the [math]\displaystyle{ p^\text{th} }[/math] persistent Betti numbers [math]\displaystyle{ \beta_p^{i,j} }[/math] are the ranks of those groups.[4] Persistent Betti numbers for [math]\displaystyle{ p=0 }[/math] coincide with the size function, a predecessor of persistent homology.[5]
Any filtered complex over a field [math]\displaystyle{ F }[/math] 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 [math]\displaystyle{ d(e_{t_i})=0 }[/math] and two-dimensional complexes with trivial homology [math]\displaystyle{ d(e_{s_j+r_j})=e_{r_j} }[/math].[6]
A persistence module over a partially ordered set [math]\displaystyle{ P }[/math] is a set of vector spaces [math]\displaystyle{ U_t }[/math] indexed by [math]\displaystyle{ P }[/math], with a linear map [math]\displaystyle{ u_t^s: U_s \to U_t }[/math] whenever [math]\displaystyle{ s \leq t }[/math], with [math]\displaystyle{ u_t^t }[/math] equal to the identity and [math]\displaystyle{ u_t^s \circ u_s^r = u^r_t }[/math] for [math]\displaystyle{ r \leq s \leq t }[/math]. Equivalently, we may consider it as a functor from [math]\displaystyle{ P }[/math] considered as a category to the category of vector spaces (or [math]\displaystyle{ R }[/math]-modules). There is a classification of persistence modules over a field [math]\displaystyle{ F }[/math] indexed by [math]\displaystyle{ \mathbb{N} }[/math]: [math]\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). }[/math] Multiplication by [math]\displaystyle{ x }[/math] 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 [math]\displaystyle{ t_i }[/math] and never disappear, while the torsion parts correspond to those that appear at filtration level [math]\displaystyle{ r_j }[/math] and last for [math]\displaystyle{ s_j }[/math] steps of the filtration (or equivalently, disappear at filtration level [math]\displaystyle{ s_j+r_j }[/math]).[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 [math]\displaystyle{ p }[/math].
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 [math]\displaystyle{ W_\infty(X,Y):= \inf_{\varphi: X \to Y} \sup_{x \in X} \Vert x-\varphi(x) \Vert_\infty, }[/math] where [math]\displaystyle{ \varphi }[/math] 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 [math]\displaystyle{ X }[/math] homeomorphic to a simplicial complex determined by the sublevel sets of a continuous tame function [math]\displaystyle{ f:X\to \mathbb{R} }[/math]. The map [math]\displaystyle{ D }[/math] taking [math]\displaystyle{ f }[/math] to the persistence diagram of its [math]\displaystyle{ k }[/math]th homology is 1-Lipschitz with respect to the [math]\displaystyle{ \sup }[/math]-metric on functions and the bottleneck distance on persistence diagrams. That is, [math]\displaystyle{ W_\infty(D(f),D(g)) \leq \lVert f-g \rVert_\infty }[/math]. [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 | 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 | 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 | 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
References
- ↑ Carlsson, Gunnar (2009). "Topology and data". AMS Bulletin 46(2), 255–308.
- ↑ Kerber, Michael; Sharathkumar, R. (2013). Cai, Leizhen; Cheng, Siu-Wing; Lam, Tak-Wah. eds. "Approximate Čech Complex in Low and High Dimensions" (in en). Algorithms and Computation. Lecture Notes in Computer Science (Berlin, Heidelberg: Springer) 8283: 666–676. doi:10.1007/978-3-642-45030-3_62. ISBN 978-3-642-45030-3. https://link.springer.com/chapter/10.1007/978-3-642-45030-3_62.
- ↑ 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. https://doi.org/10.1145/3284360.
- ↑ Edelsbrunner, H and Harer, J (2010). Computational Topology: An Introduction. American Mathematical Society.
- ↑ 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. https://link.springer.com/article/10.1007/BF00200823#page-1.
- ↑ 6.0 6.1 6.2 6.3 Barannikov, Sergey (1994). "Framed Morse complex and its invariants". Advances in Soviet Mathematics 21: 93–115. https://www.researchgate.net/publication/267672645.
- ↑ 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.
- ↑ 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.
- ↑ 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. PMID 32025466.
- ↑ Licenses here are a summary, and are not taken to be complete statements of the licenses. Some packages may use libraries under different licenses.
- ↑ 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.
- ↑ 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. https://hal.inria.fr/hal-01005601/file/RR-8548.pdf.
 |  |
