Misplaced Pages

Persistence barcode

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Technique in topological data analysis

In topological data analysis, a persistence barcode, sometimes shortened to barcode, is an algebraic invariant associated with a filtered chain complex or a persistence module that characterizes the stability of topological features throughout a growing family of spaces. Formally, a persistence barcode consists of a multiset of intervals in the extended real line, where the length of each interval corresponds to the lifetime of a topological feature in a filtration, usually built on a point cloud, a graph, a function, or, more generally, a simplicial complex or a chain complex. Generally, longer intervals in a barcode correspond to more robust features, whereas shorter intervals are more likely to be noise in the data. A persistence barcode is a complete invariant that captures all the topological information in a filtration. In algebraic topology, the persistence barcodes were first introduced by Sergey Barannikov in 1994 as the "canonical forms" invariants consisting of a multiset of line segments with ends on two parallel lines, and later, in geometry processing, by Gunnar Carlsson et al. in 2004.

Definition

Let F {\displaystyle \mathbb {F} } be a fixed field. Consider a real-valued function on a chain complex f : K → R {\displaystyle f:K\rightarrow \mathbb {R} } compatible with the differential, so that f ( σ i ) ≤ f ( τ ) {\displaystyle f(\sigma _{i})\leq f(\tau )} whenever ∂ τ = ∑ i σ i {\displaystyle \partial \tau =\sum _{i}\sigma _{i}} in K {\displaystyle K} . Then for every a ∈ R {\displaystyle a\in \mathbb {R} } the sublevel set K a = f − 1 ( ( − ∞ , a ] ) {\displaystyle K_{a}=f^{-1}((-\infty ,a])} is a subcomplex of K, and the values of f {\displaystyle f} on the generators in K {\displaystyle K} define a filtration (which is in practice always finite):

∅ = K 0 ⊆ K 1 ⊆ ⋯ ⊆ K n = K {\displaystyle \emptyset =K_{0}\subseteq K_{1}\subseteq \cdots \subseteq K_{n}=K} .

Then, the filtered complexes classification theorem states that for any filtered chain complex over F {\displaystyle \mathbb {F} } , there exists a linear transformation that preserves the filtration and brings the filtered complex into so called canonical form, a canonically defined direct sum of filtered complexes of two types: two-dimensional complexes with trivial homology d ( e a j ) = e a i {\displaystyle d(e_{a_{j}})=e_{a_{i}}} and one-dimensional complexes with trivial differential d ( e a i ′ ) = 0 {\displaystyle d(e_{a'_{i}})=0} . The multiset B f {\displaystyle {\mathcal {B}}_{f}} of the intervals [ a i , a j ) {\displaystyle [a_{i},a_{j})} or [ a i ′ , ∞ ) {\displaystyle [a_{i}',\infty )} describing the canonical form, is called the barcode, and it is the complete invariant of the filtered chain complex.

The concept of a persistence module is intimately linked to the notion of a filtered chain complex. A persistence module M {\displaystyle M} indexed over R {\displaystyle \mathbb {R} } consists of a family of F {\displaystyle \mathbb {F} } -vector spaces { M t } t ∈ R {\displaystyle \{M_{t}\}_{t\in \mathbb {R} }} and linear maps φ s , t : M s → M t {\displaystyle \varphi _{s,t}:M_{s}\to M_{t}} for each s ≤ t {\displaystyle s\leq t} such that φ s , t ∘ φ r , s = φ r , t {\displaystyle \varphi _{s,t}\circ \varphi _{r,s}=\varphi _{r,t}} for all r ≤ s ≤ t {\displaystyle r\leq s\leq t} . This construction is not specific to R {\displaystyle \mathbb {R} } ; indeed, it works identically with any totally-ordered set.

A series of four nested simplicial complexes and the 0-dimensional persistence barcode of the resulting filtration.

A persistence module M {\displaystyle M} is said to be of finite type if it contains a finite number of unique finite-dimensional vector spaces. The latter condition is sometimes referred to as pointwise finite-dimensional.

Let I {\displaystyle I} be an interval in R {\displaystyle \mathbb {R} } . Define a persistence module Q ( I ) {\displaystyle Q(I)} via Q ( I s ) = { 0 , if  s ∉ I ; F , otherwise {\displaystyle Q(I_{s})={\begin{cases}0,&{\text{if }}s\notin I;\\\mathbb {F} ,&{\text{otherwise}}\end{cases}}} , where the linear maps are the identity map inside the interval. The module Q ( I ) {\displaystyle Q(I)} is sometimes referred to as an interval module.

Then for any R {\displaystyle \mathbb {R} } -indexed persistence module M {\displaystyle M} of finite type, there exists a multiset B M {\displaystyle {\mathcal {B}}_{M}} of intervals such that M ≅ ⨁ I ∈ B M Q ( I ) {\displaystyle M\cong \bigoplus _{I\in {\mathcal {B}}_{M}}Q(I)} , where the direct sum of persistence modules is carried out index-wise. The multiset B M {\displaystyle {\mathcal {B}}_{M}} is called the barcode of M {\displaystyle M} , and it is unique up to a reordering of the intervals.

This result was extended to the case of pointwise finite-dimensional persistence modules indexed over an arbitrary totally-ordered set by William Crawley-Boevey and Magnus Botnan in 2020, building upon known results from the structure theorem for finitely generated modules over a PID, as well as the work of Cary Webb for the case of the integers.

References

  1. Ghrist, Robert (2007-10-26). "Barcodes: The persistent topology of data". Bulletin of the American Mathematical Society. 45 (1): 61–76. doi:10.1090/S0273-0979-07-01191-3. ISSN 0273-0979.
  2. ^ Barannikov, Sergey (1994). "Framed Morse complex and its invariants" (PDF). Advances in Soviet Mathematics. ADVSOV. 21: 93–115. doi:10.1090/advsov/021/03. ISBN 9780821802373. S2CID 125829976.
  3. ^ Carlsson, Gunnar; Zomorodian, Afra; Collins, Anne; Guibas, Leonidas (2004-07-08). "Persistence barcodes for shapes". Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing. Nice France: ACM. pp. 124–135. doi:10.1145/1057432.1057449. ISBN 978-3-905673-13-5. S2CID 456712.
  4. Zomorodian, Afra; Carlsson, Gunnar (2005). "Computing Persistent Homology". Discrete & Computational Geometry. 33 (2): 249–274. doi:10.1007/s00454-004-1146-y. ISSN 0179-5376.
  5. Crawley-Boevey, William (2015). "Decomposition of pointwise finite-dimensional persistence modules". Journal of Algebra and Its Applications. 14 (5): 1550066. arXiv:1210.0819. doi:10.1142/S0219498815500668. ISSN 0219-4988. S2CID 119635797.
  6. Chazal, Fréderic; de Silva, Vin; Glisse, Marc; Oudot, Steve (2016). The structure and stability of persistence modules. Switzerland. ISBN 978-3-319-42545-0. OCLC 960458101.{{cite book}}: CS1 maint: location missing publisher (link)
  7. Botnan, Magnus, and William Crawley-Boevey. "Decomposition of persistence modules." Proceedings of the American Mathematical Society 148, no. 11 (2020): 4581-4596.
  8. Webb, Cary. "Decomposition of graded modules." Proceedings of the American Mathematical Society 94, no. 4 (1985): 565-571.
Categories: