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

Multiplication by 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 and never disappear, while the torsion parts correspond to those that appear at filtration level and last for steps of the filtration (or equivalently, disappear at filtration level ).[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 .

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

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 homeomorphic to a simplicial complex determined by the sublevel sets of a continuous tame function . The map taking to the persistence diagram of its th homology is 1-Lipschitz with respect to the -metric on functions and the bottleneck distance on persistence diagrams.

That is, . [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

References

  1. Carlsson, Gunnar (2009). "Topology and data". AMS Bulletin 46(2), 255308.
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.