Source-linked AI summary
Dualities in persistent (co)homology
Vin de Silva, Dmitriy Morozov, Mikael Vejdemo-Johansson
TL;DR
The paper addresses how the four absolute and relative homology and cohomology persistence modules relate and can be computed. It establishes algebraic and global dualities, shows that one calculation run twice suffices for all four objects, and presents experiments supporting pCoh for absolute barcodes. The treatment assumes coefficients in a fixed field.
Problem
The paper asks how the four persistent homology and cohomology objects arising from filtered cell complexes relate and whether their information can be computed together.
Method
The paper develops algebraic and matrix-based dualities connecting the four persistence modules and derives pHcol, pHrow, and pCoh computational approaches.
Results
One calculation run twice suffices for all four persistent objects, while experiments support optimized pCoh for computing absolute barcodes.
Takeaways & Limitations
Existing persistent homology algorithms can process all four persistent objects, and pCoh is recommended when only the absolute barcode is required.
Takeaways & Limitations
The persistent (co)homology modules use coefficients in a fixed field; replacing the field with a ring such as Z causes complications.
Abstract
from arXiv · showhide
We consider sequences of absolute and relative homology and cohomology groups that arise naturally for a filtered cell complex. We establish algebraic relationships between their persistence modules, and show that they contain equivalent information. We explain how one can use the existing algorithm for persistent homology to process any of the four modules, and relate it to a recently introduced persistent cohomology algorithm. We present experimental evidence for the practical efficiency of the latter algorithm.
1. Introduction
The paper relates four persistent homology and cohomology objects through algebraic and global dualities, reducing their computation to one calculation run twice. It also identifies an optimized cohomology algorithm as the preferred choice when only absolute barcodes are needed.
- Motivation: For inverse problems and applications such as geological sonar, persistent homology extracts robust topological information about features before their geometric shape is known.Classical transform-based methods can require substantial regularization or data cleaning in nonlinear, ill-posed, or ill-conditioned settings.
- Contributions: Persistent absolute and relative homology and cohomology have equivalent barcode information, while their cycles, cocycles, and bounding chains or cochains are related.Absolute and relative barcodes determine one another, and corresponding representatives determine one another.
- Contributions: Global duality interchanges persistent absolute homology with persistent relative cohomology after transforming the input data.Unlike pointwise homology–cohomology duality, global duality is specific to persistent topology and commutes with algorithms and theorems.
- Algorithms: A single calculation, run twice, suffices to compute all four persistent objects using either the pHcol column algorithm or the pHrow row algorithm.The preferred algorithm depends on whether rows or columns of the boundary matrix are easier to access.
- Experiments: When only the absolute barcode is required, experiments support using the optimized pHrow variant pCoh instead of standard pHcol.The paper calls on library writers to implement pCoh and users to employ it.
2. Algebra
The paper works with homology theory over a fixed field and treats persistent (co)homology as graded modules over a polynomial ring.
- Assumptions: The discussion assumes familiarity with homology theory and prefers cellular homology because it is more general than simplicial homology.The coefficient field k remains fixed throughout the paper.
- Assumptions: Persistent (co)homology has the structure of a graded module over k[t], whereas replacing the field with a ring such as Z introduces complications.The paper explicitly limits its coefficient setting to a fixed field.
2.2. Filtered complexes.
A filtered cell complex is built by adding one cell at a time, with nondecreasing filtration values assigned to the cells.
- Filtered complexes: A filtered cell complex begins with a vertex and forms each subsequent complex by adjoining one cell to the previous complex.The filtration is indexed by {1, 2, ..., n}.
- Filtered complexes: The filtration assigns real values a1 ≤ a2 ≤ ··· ≤ an to the cells’ indices.These values determine the ordered progression through the filtered complexes.
- Example: The paper uses a cellular filtration of the 2-sphere with six cells appearing at times ai = i.The example provides a concrete instance of the one-cell-at-a-time construction.
2.3. Persistent homology.
Applying homology to a filtered complex produces a persistence module whose interval decomposition is summarized by a barcode. The paper compares absolute and relative homology and cohomology sequences within this framework.
- Persistence modules: Applying a homology functor to a filtered complex yields finite-dimensional vector spaces and linear maps known as a persistence module.The functor may denote k-dimensional or total homology.
- Interval decomposition: A persistence module decomposes into interval modules [p, q], each representing a feature that persists across a consecutive index range.Intervals can also be written as half-open real intervals [ap, aq+1), with an+1 = ∞.
- Barcode: The barcode is the multiset of interval-module index pairs or their corresponding half-open real intervals.Intervals with equal birth and death values are customarily discarded.
- Example: For the filtered 2-sphere example, the total homology barcode is {[1, ∞)0, [2, 3)0, [4, 5)1, [6, ∞)2}.The subscripts identify the homological dimensions of the features.
- Four persistent objects: The four natural sequences include absolute homology, absolute cohomology, relative homology, and relative cohomology.Persistent homology and cohomology have the same barcodes, although cycles and cocycles differ.
2.4. The four standard persistence modules.
The section specifies persistence diagrams for the four standard modules and illustrates a relative-homology interval. It also motivates formalizing the relationship between absolute and relative barcodes.
- Persistence diagrams encode intervals with index ranges that differ between absolute and relative homology or cohomology.Absolute diagrams use 1 ≤ p ≤ q ≤ n, whereas relative diagrams use 0 ≤ p ≤ q ≤ n − 1.
- The running example gives Pers(H∗(S6, S)) as four intervals, including [0, 5) in dimension 2.The displayed integer-pair representation is translated into half-open intervals [−∞, 1), [2, 3), [4, 5), and [−∞, 6).
- At index 2, an arc connecting the two points of S2 represents a nontrivial H1 class that vanishes at index 3.This class is [σ3] = [σ4] and generates the interval [2, 3).
- The observed relationship between absolute and relative homology barcodes is formalized in the next section.
2.5. Barcode isomorphisms.
This section establishes barcode equivalences across absolute and relative homology and cohomology, with dimension shifts for finite intervals and endpoint reversal for certain infinite intervals. Consequently, any of the four persistence modules can be used when only barcode information is required.
- Homology–cohomology isomorphisms: Absolute homology and cohomology have identical barcodes, and the same holds for relative homology and cohomology.The cohomology result follows from the universal coefficients theorem, natural isomorphisms, and equality of ranks.
- Notation: Finite and infinite barcode parts are separated into Pers0 and Pers∞, respectively.Pers0 contains finite intervals, while Pers∞ contains intervals with one infinite endpoint.
- Absolute–relative isomorphisms: Persistent homology and relative homology barcodes carry the same information, with a dimension shift for finite intervals.The finite parts correspond directly, while infinite intervals are related by the bijection [a, ∞) ↔ [−∞, a).
- Consequences: All four barcodes carry exactly the same information after accounting for dimension shifts, so calculations may use whichever module is convenient.The concatenated sequence is distinct from extended persistence, whose relative half reverses the cells.
- Concatenated sequence: The concatenated sequence Hk(X) → Hk(X∞, X) contains ordinary finite intervals, dimension-shifted relative intervals, and intervals joining absolute and relative halves.Its interval collection includes [a, b), [ā, b̄), and [a, ā) types, with the latter representing infinite absolute intervals.
2.6. Persistent chain complexes.
The section represents persistent homology through filtered chain complexes and decomposes the complexes into generators that produce persistence intervals. This decomposition explains the corresponding absolute–relative interval relationships and the structural pairing of persistence modules.
- Filtered chain complexes: A filtered cell complex yields chain complexes whose boundary maps restrict to each filtration stage and define persistent absolute homology.The boundary operator satisfies ∂2 = 0, and each filtered subcomplex inherits its restricted boundary map.
- Global duality: Absolute homology and relative cohomology are structurally akin, whereas absolute cohomology and relative homology have opposite injective or surjective map patterns.The paper identifies this contrast as a symptom of global duality.
- Basis decomposition: A new basis decomposes the chain complex into unpaired generators and paired two-generator complexes whose boundaries satisfy ∂σ̂h = σ̂g.The resulting persistence intervals are [af, ∞) for unpaired generators and [ag, ah) for paired generators.
- Relative intervals: In the relative complex, an unpaired generator contributes [−∞, af), while a paired summand contributes [ag, ah) in one higher homological dimension than its absolute counterpart.These correspondences explain the infinite-interval reversal and finite-interval dimension shift.
2.7. Cohomology.
Persistent cohomology is obtained from reversed dual chain sequences, making it structurally parallel to persistent homology and allowing existing algorithms to compute it.
- Reversing the sequence and replacing cells and boundaries with formal dual cells and coboundaries converts persistent absolute homology computation into persistent relative cohomology computation.
- Applying the same construction to the dual sequence computes persistent absolute cohomology from an algorithm for persistent relative homology.
- The duality requires reversing interval indices: [p, q −1] becomes [n + 1 −q, n −p], corresponding to [a_n+1−q, a_n+1−p).
- The resulting correspondence relates persistence pairings through (s, t) in the dual sequence exactly when (n + 1 −t, n + 1 −s) pairs in the original sequence.
2.8. A remark for the algebraically-minded.
The algebraic viewpoint treats persistence modules as graded k[t]-modules and defines dual constructions that transport boundary maps contravariantly.
- A persistence module is viewed as a graded module over k[t], with the filtered chain complex freely generated by cells assigned filtration degrees.
- Duals can be taken over the ground field k or polynomial ring k[t], yielding the paper’s global dual constructions.
- The dual operations are contravariant functors, so the original boundary map induces boundary maps on the resulting dual modules.
3. Matrix Algorithms
Matrix anti-transposition represents the dual persistence objects, while matrix reduction supplies intervals, generators, and two equivalent computational algorithms.
- 3. Matrix Algorithms: The boundary matrix D encodes the filtered chain complex, with each column representing a cell boundary and leading principal submatrices representing filtration stages.
- 3. Matrix Algorithms: Anti-transposing D produces D⊥, which represents persistent relative cohomology and reverses the filtration through its principal submatrices.
- 3. Matrix Algorithms: Any procedure extracting intervals and generators from D for absolute or relative homology does the corresponding job for relative or absolute cohomology on D⊥.
- 3. Matrix Algorithms: In a reduced decomposition R = DV, lowR determines persistence pairings, while columns of V and R provide cycles and bounding chains.
- 3. Matrix Algorithms: The same matrix framework reads cohomology cocycles and their intervals from R⊥ = D⊥V⊥, with starred indices accounting for reversed cell labels.
- 3. Matrix Algorithms: The column algorithm pHcol and row algorithm pHrow produce identical decompositions, provided row reduction updates only the columns selected by the persistence pairing.
4. Optimizations
The persistent cohomology algorithm pCoh is an optimized view of the row algorithm on the dual matrix, reducing retained information and improving measured performance.
- 4. Optimizations: pCoh can be viewed as an optimization of pHrow applied to the anti-transposed matrix D⊥.
- 4. Optimizations: pCoh maintains cocycles in right-filtration order and drops each cocycle once its persistence pairing is determined.
- 4. Optimizations: The maintained cocycle basis equals the bottom-right corner of V⊥ during the corresponding row-algorithm iteration.
- 4. Optimizations: 2,171,909,275 operations and 106 s were measured for pCoh on M-50, versus 609,477,028,616 operations and 4160 s for pHcol.
- 4. Optimizations: 55,930,317 operations and 6 s were measured for pCoh on T-10,000, versus 29,760,159,689 operations and 207 s for pHcol.
- 4. Optimizations: The authors conclude that, when given a choice, the cohomology algorithm is generally preferable, especially when computing only persistence diagrams.