An Elementary Algorithm for Persistent Cohomology

The problem

Consider two simplicial complexes X and Y as pictured below.

Our goal is to understand an algorithm which reveals how a map of complexes induces a map on (co)homology.

This post is laid out in the following two parts:

We will start by reviewing an algorithm others have shared for computing the basis for homology: i.e. given matrices multiplying to zero, A・B = 0, we compute a basis for the quotient space ker(A) / im(B).
The above simplicial complexes come with an inclusion map X → Y, which gives a map of cochain complexes, C(X) → C(Y), and thus a map on cohomology H(X) → H(Y). We will show how to make the above algorithm give a map of bases on cohomology which is useful in persistent cohomology, for example.

Computing the Homology of AB=0

Given two matrices whose product is zero, A・B = 0, we review a process in general which computes a basis for ker(A) / im(B) as found in this post and the follow up post by Jeremy Kun. A condensed version of the steps are:

First augment A over the identity matrix I, and column reduce¹ it to obtain A・Q augmented over I・Q = Q. As shown below, this process produces a basis for ker(A) but is not yet combatible with im(B).
Now apply Q^-1 to B as row operations via Q^-1・B. Since this matrix is not necessarily fully reduced, we can not just read off pivots. Instead we now finish row-reducing B in the form of P・Q^-1・B.
Finally, we apply P^-1 to our kernel basis by A・Q・P^-1. At this point we can read off the two bases: one for im(B) which sits inside the basis for ker(A).

The example that we use below comes from computing H(Y) where B: C⁰(Y) → C¹(Y) and A: C¹(Y) → C²(Y).

As outlined above, first we column reduce (see the footnotes² for steps) A by A・Q in our first step toward computing a basis for ker(A).

The labels with two indices correspond to the edges of the simplicial complex Y, and the labels with the three indices correspond to the filled in triangles for Y. The five highlighted column vectors of Q form a basis for ker(A). However, this basis is not compatible with any basis for im(B) yet. Notice that the first and third columns of Q are not part of the basis for ker(A)…

Next, we apply Q^-1・B en route to a basis for im(B).

Notice that the first and third rows are all zeros, and thus do not contribute to the image basis, and that these correspond to the first and third columns of Q. However these rows are not yet linearly independent so we need to further row-reduce (see the footnotes³ for steps).

The circled values tell us which rows are the pivot rows, and we label this set of rows S={y₂, y₄, y₆, y₇}. Once we apply P^-1 to our initial kernel basis by A・Q・P^-1 we will have a new kernel basis which is compatible with S:

Finally we have the desired bases. The column vectors of Q・P^-1 above which are circled provide us a basis for the kernel of A. They are y₂= u₀₁ + u₀₂, y₄ = -u₀₁ + u₁₂ + u₁₃ + u₁₄, y₅=u₁₄, y₆ = u₀₁ – u₁₂ + u₂₃, and y₇ = u₃₄. So our preferred basis for ker(A) is T = { y₂, y₄, y₅, y₆, y₇ } while recall that our basis for im(B) was the subset S={y₂, y₄, y₆, y₇}. Thus the basis for the cohomology ker(A) / im(B) is the singleton set of classes { [y₅] }.

An algorithm for maps of (co)homology of filtered complexes

The following two constructions induce computationally-equivalent quotient (vector) spaces to compute:

Given a data set, $D \subset \mathbb{R}^n$ , for each real number ε we define a simplicial (Čech) complex X^ε as follows. The vertices are the data points p_i. Now center at each point an open epsilon ball. The edges p_ij are the pairs of points whose epsilon balls intersect. The triangles p_ijk are the triples of points whose epsilon balls triple-intersect. And so on… Construct the usual chain complex by defining boundary maps to be the alternating sums of the face maps. Call these boundary maps $\delta^{\epsilon}_p: X^{\epsilon}_p \to X^{\epsilon}_{p-1}$ and consider their transposes, $\delta_{\epsilon}^p:= \left(\delta^{\epsilon}_p\right)^T: X_{\epsilon}^{p-1}=X^{\epsilon}_{p-1} \to X^{\epsilon}_{p}= X_{\epsilon}^{p}$ . Define the (Čech) cohomology by $H^p (X_{\epsilon}) = ker(\delta^p_{\epsilon}) / im(\delta^{p-1}_{\epsilon})$ . Now for each pair of resolutions ε < ε’ we get an induced map H(X^ε’) → H(X^ε). Explicitly analyzing which classes get sent to which classes under this map is the context of this post.
Given a topological space, X, consider a finite open cover U= {U_i}_i𝜖I and define the Čech cochain complex⁴ as follows. The zero cochain vector space Č⁰(U) is the free vector on the elements of the open cover. The pth cochain vector space Č^p(U) is the free vector space on the (p+1)-fold intersection of the elements $U_{i_0 \dots i_p}$ of the open cover. The boundary maps are defined are defined component wise as follows: $\delta^p(\sum \alpha_{j_0 \cdots j_p}\cdot U_{j_0 \cdots j_p} )_{i_0 \dots i_{p+1}} = \sum_{j=0}^{p+1} (-1)^j \alpha_{i_0 \dots \hat{i_j} \dots i_{p+1}}$ where $\hat{i_j}$ means the index is removed. Define the (Čech) cohomology by $H^p(U)= ker(\delta_U^p) / im(\delta_U^{p-1})$ . Now for each pair of covers $V \hookrightarrow U$ we get an induced map $H(U) \to H(V)$ . Explicitly analyzing which classes get sent to which classes under this map is equivalent to the context of this post.

So whichever context you prefer, we now want to see how to compute bases for the cohomology of the simplicial complexes C(X) and C(Y) above. Let’s focus on H¹. The computations involving the matrices A and B from the previous section, using either of the first context written immediately above in this section, with X representing resolution ε and Y representing ε’, we have $A = \delta_{\epsilon}^1$ and $B = \delta_{\epsilon}^0$ . So the above computation is computing H¹(Y) = H¹(X^ε’). To compute H¹(X^ε) and simultaneously analyze the map H¹(X^ε’) → H¹(X^ε) we see that the map of cochain complexes amounts to sending basis elements to zero if the simplex is no longer represented⁵. Below we call this map I_X since it is like the identity on most basis elements but for some simplices the basis element is sent to zero.

Thus we are going to merely apply the transformations P and Q as above but now to the boundary maps for X = X^ε:

As with computing the basis for ker(A) above, the columns below the zeros of $\delta^1_X \cdot I_X \cdot Q \cdot P^{-1}$ form a basis for $\delta^1_X$ . In this case those columns are x₂ = v₀₁, x₃ = -v₀₁ + v₁₂, x₄ = -v₀₁ + v₁₂ + v₁₃, x₆ = v₀₁ – v₁₂ + v₂₃. Notice that x₅ and x₇ are trivial. So the basis for the kernel is D = {x₂, x₃, x₄, x₆}. Of these basis vectors, those which are contributing to the image (seen in the matrix of rows for $P Q^{-1} \delta^0_X$ ) are E = {x₂, x₄, x₆}. If these were not linearly independent we would have to perform further row reduction R and corresponding column operations R^-1 to the kernel basis. However, these basis vectors for the image are linearly independent in the image and so we have the singleton class basis for homology H¹(X) = { [x₃]}.

Under the map H(Y) = {[y₅=u₁₄]}→ H(X) = {[x₃ = -v₀₁ + v₁₂]}, we see that y₅=u₁₄ gets sent to zero and x₃ = -v₀₁ + v₁₂ is not in the image. In the language of persistence this corresponds to the fact that the loop in the complex for X “dies” when we move to the complex Y, and a new loop is “born”!

⃞

Footnotes

It turns out that during this algorithm, reduction should only ever take the form of scaling or “column j is replaced by column j added to a scalar multiple of column i” with i < j (similar for row operations. Swapping rows/columns or applying the above operation with i greater than or equal to j will cause consistency issues.
The column reductions are given by the following steps: (i) col₂ += col₁, (ii) col₃ += -col₁, (iii) col₄ += col₃, (iv) col₆ += -col₃.
The row reductions are given by the following step: (i) row₄ += -row₃.
I’m translating for the special case where we are taking the Čech complex for the sheaf of locally constant real-valued functions.
Our setup has the property that for ε < ε’ the complex X^ε is a subcomplex of X^ε’.

An Elementary Algorithm for Persistent Cohomology

The problem

Computing the Homology of AB=0

An algorithm for maps of (co)homology of filtered complexes

Footnotes

Published by Cheyne Glass

Leave a Reply Cancel reply

An Elementary Algorithm for Persistent Cohomology

The problem

Computing the Homology of AB=0

An algorithm for maps of (co)homology of filtered complexes

Footnotes

Share this:

Like this:

Published by Cheyne Glass

Leave a Reply Cancel reply