Persistent cohomology user manual¶

Definition¶

Author: Clément Maria

Introduced in: GUDHI PYTHON 2.0.0

Copyright: GPL v3

Please refer to each data structure that contains persistence feature for reference:

Computation of persistent cohomology using the algorithm of [6] and [7] and the Compressed Annotation Matrix implementation of [8].

The theory of homology consists in attaching to a topological space a sequence of (homology) groups, capturing global topological features like connected components, holes, cavities, etc. Persistent homology studies the evolution – birth, life and death – of these features when the topological space is changing. Consequently, the theory is essentially composed of three elements:

topological spaces
their homology groups
an evolution scheme.

Topological Spaces¶

Topological spaces are represented by simplicial complexes. Let \(V = \{1, \cdots ,|V|\}\) be a set of vertices. A simplex \(\sigma\) is a subset of vertices \(\sigma \subseteq V\). A simplicial complex \(\mathbf{K}\) on \(V\) is a collection of simplices \(\{\sigma\}\), \(\sigma \subseteq V\), such that \(\tau \subseteq \sigma \in \mathbf{K} \Rightarrow \tau \in \mathbf{K}\). The dimension \(n=|\sigma|-1\) of \(\sigma\) is its number of elements minus 1. A filtration of a simplicial complex is a function \(f:\mathbf{K} \rightarrow \mathbb{R}\) satisfying \(f(\tau)\leq f(\sigma)\) whenever \(\tau \subseteq \sigma\).

Homology¶

For a ring \(\mathcal{R}\), the group of n-chains, denoted \(\mathbf{C}_n(\mathbf{K},\mathcal{R})\), of \(\mathbf{K}\) is the group of formal sums of n-simplices with \(\mathcal{R}\) coefficients. The boundary operator is a linear operator \(\partial_n: \mathbf{C}_n(\mathbf{K},\mathcal{R}) \rightarrow \mathbf{C}_{n-1}(\mathbf{K},\mathcal{R})\) such that \(\partial_n \sigma = \partial_n [v_0, \cdots , v_n] = \sum_{i=0}^n (-1)^{i}[v_0,\cdots ,\widehat{v_i}, \cdots,v_n]\), where \(\widehat{v_i}\) means \(v_i\) is omitted from the list. The chain groups form a sequence:

\[\cdots \ \ \mathbf{C}_n(\mathbf{K},\mathcal{R}) \xrightarrow{\ \partial_n\ } \mathbf{C}_{n-1}(\mathbf{K},\mathcal{R}) \xrightarrow{\partial_{n-1}} \cdots \xrightarrow{\ \partial_2 \ } \mathbf{C}_1(\mathbf{K},\mathcal{R}) \xrightarrow{\ \partial_1 \ } \mathbf{C}_0(\mathbf{K},\mathcal{R})\]

of finitely many groups \(\mathbf{C}_n(\mathbf{K},\mathcal{R})\) and homomorphisms \(\partial_n\), indexed by the dimension \(n \geq 0\). The boundary operators satisfy the property \(\partial_n \circ \partial_{n+1}=0\) for every \(n > 0\) and we define the homology groups:

\[\mathbf{H}_n(\mathbf{K},\mathcal{R}) = \ker \partial_n / \mathrm{im} \ \partial_{n+1}\]

We refer to [12] for an introduction to homology theory and to [13] for an introduction to persistent homology.

Indexing Scheme¶

“Changing” a simplicial complex consists in applying a simplicial map. An indexing scheme is a directed graph together with a traversal order, such that two consecutive nodes in the graph are connected by an arrow (either forward or backward). The nodes represent simplicial complexes and the directed edges simplicial maps.

From the computational point of view, there are two types of indexing schemes of interest in persistent homology:

linear ones \(\bullet \longrightarrow \bullet \longrightarrow \cdots \longrightarrow \bullet \longrightarrow \bullet\) in persistent homology [14],
zigzag ones \(\bullet \longrightarrow \bullet \longleftarrow \cdots \longrightarrow \bullet \longleftarrow \bullet\) in zigzag persistent homology [15].

These indexing schemes have a natural left-to-right traversal order, and we describe them with ranges and iterators. In the current release of the Gudhi library, only the linear case is implemented.

In the following, we consider the case where the indexing scheme is induced by a filtration.

Ordering the simplices by increasing filtration values (breaking ties so as a simplex appears after its subsimplices of same filtration value) provides an indexing scheme.

Examples¶

We provide several example files: run these examples with -h for details on their use.

Bibliography¶

1: Alon Efrat, Alon Itai, and Matthew J. Katz. Geometry helps in bottleneck matching and related problems. Algorithmica, 31(1):1–28, 2001.
2: Michael Kerber, Dmitriy Morozov, and Arnur Nigmetov. Geometry helps to compare persistence diagrams. J. Exp. Algorithmics, 22:1.4:1–1.4:20, September 2017. URL: http://doi.acm.org/10.1145/3064175, doi:10.1145/3064175.
3: T. Kaczynski, K. Mischaikow, and M. Mrozek. Computational Homology. Applied Mathematical Sciences. Springer New York, 2004. ISBN 9780387408538. URL: https://books.google.fr/books?id=AShKtpi3GecC.
4: Hubert Wagner, Chao Chen, and Erald Vucini. Efficient Computation of Persistent Homology for Cubical Data, pages 91–106. Mathematics and Visualization. Springer Berlin Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-23175-9_7, doi:10.1007/978-3-642-23175-9_7.
5: Jean-Daniel Boissonnat and Clément Maria. The simplex tree: an efficient data structure for general simplicial complexes. Algorithmica, pages 1–22, 2014. URL: http://dx.doi.org/10.1007/s00453-014-9887-3, doi:10.1007/s00453-014-9887-3.
6: Vin de Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Persistent cohomology and circular coordinates. Discrete & Computational Geometry, 45(4):737–759, 2011.
7: Tamal K. Dey, Fengtao Fan, and Yusu Wang. Computing topological persistence for simplicial maps. CoRR, 2012.
8: Jean-Daniel Boissonnat, Tamal K. Dey, and Clément Maria. The compressed annotation matrix: an efficient data structure for computing persistent cohomology. In ESA, 695–706. 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_59, doi:10.1007/978-3-642-40450-4_59.
9: Mathieu Carrière, Bertrand Michel, and Steve Oudot. Statistical Analysis and Parameter Selection for Mapper. CoRR, 2017.
10: Tamal Dey, Fengtao Fan, and Yusu Wang. Graph induced complex on point data. In Proceedings of the Twenty-ninth Annual Symposium on Computational Geometry, 107–116. 2013.
11: Mathieu Carrière and Steve Oudot. Structure and Stability of the 1-Dimensional Mapper. CoRR, 2015.
12: James R. Munkres. Elements of algebraic topology. Addison-Wesley, 1984. ISBN 978-0-201-04586-4.
13: Herbert Edelsbrunner and John Harer. Computational Topology - an Introduction. American Mathematical Society, 2010. ISBN 978-0-8218-4925-5.
14: Afra Zomorodian and Gunnar E. Carlsson. Computing persistent homology. Discrete & Computational Geometry, 33(2):249–274, 2005.
15: Gunnar E. Carlsson and Vin de Silva. Zigzag persistence. Foundations of Computational Mathematics, 10(4):367–405, 2010.