Persistent Homology
   HOME

TheInfoList



OR:

:''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. To find the persistent homology of a space, the space must first be represented as a
simplicial complex In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial set ...
. A distance function on the underlying space corresponds to a
filtration Filtration is a physical separation process that separates solid matter and fluid from a mixture using a ''filter medium'' that has a complex structure through which only the fluid can pass. Solid particles that cannot pass through the filter ...
of the simplicial complex, that is a nested sequence of increasing subsets.


Definition

Formally, consider a real-valued function on a simplicial complex f:K \rightarrow \mathbb 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 the sublevel set K_a=f^((-\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 \cdots \subseteq K_n = K When 0\leq i \leq j \leq n, the inclusion K_i \hookrightarrow K_j induces a group homomorphism, homomorphism f_p^:H_p(K_i)\rightarrow H_p(K_j) on the simplicial homology groups for each dimension p. The p^\text persistent homology groups are the images of these homomorphisms, and the p^\text persistent
Betti numbers In algebraic topology, the Betti numbers are used to distinguish topological spaces based on the connectivity of ''n''-dimensional simplicial complexes. For the most reasonable finite-dimensional spaces (such as compact manifolds, finite simplicia ...
\beta_p^ are the ranks of those groups. Persistent Betti numbers for p=0 coincide with the
size function Size functions are shape descriptors, in a geometrical/topological sense. They are functions from the half-plane x to the natural numbers, counting certain
, a predecessor of persistent homology. Any filtered complex over a field 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 d(e_)=0 and two-dimensional complexes with trivial homology d(e_)=e_. 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^r_t 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: U \simeq \bigoplus_i x^ \cdot F \oplus \left(\bigoplus_j x^ \cdot (F (x^\cdot F )\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). 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, where each generator is represented by a segment connecting the birth and the death values plotted on separate lines for each 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 W_\infty(X,Y):= \inf_ \sup_ \Vert x-\varphi(x) \Vert_\infty, where \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 X homeomorphic to a simplicial complex determined by the sublevel sets of a continuous tame function f:X\to \mathbb. The map D taking f to the persistence diagram of its kth homology is 1-Lipschitz with respect to the \sup-metric on functions and the bottleneck distance on persistence diagrams. That is, W_\infty(D(f),D(g)) \leq \lVert f-g \rVert_\infty.


Computation

There are various software packages for computing persistence intervals of a finite filtration. The principal algorithm is based on the bringing of the filtered complex to its canonical form by upper-triangular matrices.


See also

* Topological data analysis * Computational topology


References

{{reflist Homology theory Computational topology