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.
Definition[]
Formally, consider a real-valued function on a simplicial complex that is non-decreasing on increasing sequences of faces, so whenever is a face of in . Then for every the sublevel set is a subcomplex of K, and the ordering of the values of on the simplices in (which is in practice always finite) induces an ordering on the sublevel complexes that defines a filtration
When , the inclusion induces a homomorphism on the simplicial homology groups for each dimension . The persistent homology groups are the images of these homomorphisms, and the persistent Betti numbers are the ranks of those groups.[2] Persistent Betti numbers for coincide with the size function, a predecessor of persistent homology.[3]
Any filtered complex over a field 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 and two-dimensional complexes with trivial homology .[4]
A persistence module over a partially ordered set is a set of vector spaces indexed by , with a linear map whenever , with equal to the identity and for . Equivalently, we may consider it as a functor from considered as a category to the category of vector spaces (or -modules). There is a classification of persistence modules over a field indexed by :
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 .
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
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.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 | ||
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[]
- ^ 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.
- ^ a b c d Barannikov, Sergey (1994). "Framed Morse complex and its invariants". Advances in Soviet Mathematics. 21: 93–115.
- ^ 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. PMC 6979512. 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. ISSN 0302-9743.
- ^ 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.
- Homology theory
- Computational topology