Computing persistent homology of filtrations

We consider now the computational aspects.

For $2$-dimensional gray scale images, this approach to homology and persistence has been used in an image analysis program called Pixcavator considered elsewhere.

The algorithm has complexity of $O(n^{2}),$ where $n$ is the number of pixels in the image.

For the general case, the analysis algorithm may be outlined as follows:

• The input is a filtration.
• The homology groups of its members and the homomorphisms induced by inclusions are computed.
• The homology group of the filtration is computed.
• The persistence of all elements of the homology groups is computed.
• The user sets a threshold $p$ for persistence and the $p$-noise group of the filtration is computed.
• The $p$-persistent homology group of the filtration is computed and given as output.

If the user changes the threshold, the last step is repeated as necessary without repeating the rest.

The algorithm above computes the homology group of filtration, as defined, incrementally. This may be both a disadvantage and an advantage.

In comparison, the persistence complex also contains information about all homology classes of the filtration but its computation does not require computing the homology of each complex of the filtration. Meanwhile, the above algorithm may have to compute the same homology over and over if consecutive complexes are identical. Hence, the algorithm has a disadvantage in terms of processing time.

On the other hand, the incremental nature of the algorithm makes its use of memory independent from the length of the filtration. Another advantage is that multi-parameter filtrations are dealt with in the exact same manner (see next section).

The inefficiency of the above algorithm can be addressed with a proper algebraic tool. This tool is the mapping cone:

Suppose, for simplicity, that our filtration has only two elements: $$i:K^{1}\hookrightarrow K^{2}.$$ The mapping cone is, in a sense, a combination of the kernel and the cokernel of $i_{\ast }$. It captures the difference between $K^{1}$ and $K^{2}$ on the chain level: everything in $C_{\ast }(K^{1})$ is killed unless it also appears in $C_{\ast }(K^{2})$ under $i_{\ast }$. Then the algorithm is to construct the homology group from the chain complexes $C_{\ast }(K^{1}),C_{\ast }(K^{2})$ of the elements of the filtration and the chain map $i_{\ast }:C_{\ast }(K^{1})\rightarrow C_{\ast}(K^{2}).$

Definition. The topological mapping cone is $$TC(\{K^{1},K^{2}\})=(K^{1}\times \lbrack 0,1])/(K^{1}\times \{0\})\sqcup K^{2}/_{x\sim i(x)}.$$

The idea is that the topological mapping cone captures the difference between $K^{1}$ and $K^{2}$: everything in $K^{1}$ is killed unless it also appears in $K^{2}$ under $i.$ Now, the mapping cone captures this difference chainwise: everything in $C_{\ast }(K^{1})$ is killed unless it also appears in $C_{\ast }(K^{2})$ under $i_{\ast }$.

Given a filtration, is there a complex with its homology equal to the homology of the filtration?

The goal is to construct this group from the chain complexes of the elements of the filtration $C_{\ast }(K^{1}),C_{\ast }(K^{2})$ and the chain map $i_{\ast }.$ On the chain level we have:

\begin{equation*} \begin{matrix}{} \downarrow ^{\partial _{1}} & & \downarrow ^{\partial _{2}} \\ C_{2}(K^{1}) & ^{\underrightarrow{~\,i_{\ast }~~}} & C_{2}(K^{2}) \\ \downarrow ^{\partial _{1}} & & \downarrow ^{\partial _{2}} \\ C_{1}(K^{1}) & ^{\underrightarrow{~\,i_{\ast }~~}} & C_{1}(K^{2}) \\ \downarrow ^{\partial _{1}} & & \downarrow ^{\partial _{2}} \\ C_{0}(K^{1}) & ^{\underrightarrow{~\,i_{\ast }~~}} & C_{0}(K^{2}) \end{matrix}% \end{equation*}

Definition. The mapping cone $C(\{K^{1},K^{2}\})$ of the filtration above is the following chain complex: \begin{equation*} \begin{matrix}{} & \downarrow ^{\partial } & \\ C_{2}(K^{1}) & \oplus & C_{1}(K^{2}) \\ & \downarrow ^{\partial } & \\ C_{1}(K^{1}) & \oplus & C_{0}(K^{2}) \\ & \downarrow ^{\partial } & \\ C_{0}(K^{1}) & \oplus & 0, \end{matrix} \end{equation*} where the boundary operator $\partial $ is given by \begin{equation*} \partial =\left[ \begin{array}{cc} d & 0 \\ i_{1} & \partial _{2} \end{array} \right] \end{equation*} acting on column vectors, $d$ is the boundary operator of the "shifted" chain complex $C_{n}=C_{n+1}(K^{1})$ of the first cell complex given by

• $d^{n}=-\partial _{1}^{n+1},$ and
• $i_{1}:C_{n}(K^{1})\rightarrow C_{n}$ is the shift of $i_{\ast }.$

Then $$\partial ^{n}(\alpha ^{n+1},\beta ^{n})=(-\partial _{1}^{n+1}(\alpha^{n+1}),i_{\ast }^{n+1}(\alpha ^{n+1})+\partial _{2}^{n}(\beta ^{n})).$$

Our main reason for using the mapping cone is the following.

Proposition. If $$\tilde{H}_{\ast }(C(\{K^{1},K^{2}\}))=0,$$ then $$i_{\ast }:H_{\ast}(K^{1})\rightarrow H_{\ast }(K^{2})$$ is an isomorphism (both kernel and cokernel are $0$).

In other words, if the mapping cone is acyclic, $K^{2}$ does not contribute anything to the homology of the filtration.

Proposition. The singular chain complex of the topological mapping cone is homotopy chain equivalent to the mapping cone.

Recall, the homology group of the filtration is $$H_{\ast }(\{K^{1},K^{2}\})=\ker i_{\ast }\oplus H_{\ast }(K^{2}).$$

Theorem. The homology group of filtration $\{K^{1},K^{2}\}$ with two elements is isomorphic to the homology group of the direct sum of the chain complex $C_{\ast }(K^{1})$ of $K^{1}$ and the mapping cone of the filtration: $$H_{\ast }(\{K^{1},K^{2}\})=H_{\ast }(C_{\ast }(K^{1})\oplus C(\{K^{n}\})).$$

We can also provide an explicit representation of the chain complex of the mapping cone: \begin{equation*} \begin{matrix}{} ... & & ... & & ... & & \\ \downarrow ^{\partial _{1}} & & \downarrow ^{\partial } & & \downarrow ^{\partial _{2}} & & \\ C_{2}(K^{1}) & \oplus & C_{3}(K^{2}) & \oplus & C_{2}(K^{2}) & & \\ \downarrow ^{\partial _{1}} & & \downarrow ^{\partial } & & \downarrow ^{\partial _{2}} & & \\ C_{1}(K^{1}) & \oplus & C_{2}(K^{1}) & \oplus & C_{2}(K^{2}) & & \\ \downarrow ^{\partial _{1}} & & \downarrow ^{\partial } & & \downarrow ^{\partial _{2}} & & \\ ... & & ... & & ... & & \end{matrix} \end{equation*} Its boundary operator is $$D^{n}(a^{n},b^{n+1},c^{n})=(\partial _{1}^{n}(a^{n}),-\partial_{1}^{n+1}(b^{n+1}),i_{\ast }^{n+1}(b^{n+1})+\partial _{1}^{n}(c^{n})).$$

Repetition:

Now the definition and the meaning of the mapping cone of a general filtration is clear. Suppose we have a one-parameter filtration $$K^{1}\hookrightarrow K^{2}\hookrightarrow K^{3}\hookrightarrow K^{4}\hookrightarrow \ldots \ \hookrightarrow K^{s}.$$

Now, once we know the cone $C(\{K^{1},K^{2}\})$ we add $K^{3}$ to the list and compute the new mapping cone for the two chain complexes $C(\{K^{1},K^{2}\})$ and $C_{\ast }(K^{3}).$ The resulting chain complex is \begin{eqnarray*} &&(C_{\ast +1}(K^{1})\oplus C_{\ast }(K^{2}))_{\ast +1}\oplus C_{\ast }(K^{3}) \\ &=&C_{\ast +2}(K^{1})\oplus C_{\ast +1}(K^{2})\oplus C_{\ast }(K^{3}). \end{eqnarray*} The boundary operator is... to be computed.

Definition. The mapping cone of filtration $\{K^{n}\}$ is the following chain complex: $$C(\{K^{n}\})=C_{\ast +s}(K^{1})\oplus C_{\ast +s-1}(K^{2})\oplus ...\oplus C_{\ast +1}(K^{s-1})\oplus C_{\ast }(K^{s})$$ with the boundary operator given by $$??$$

Corollary. The homology group of filtration $\{K^{n}\}$ is isomorphic to the homology group of the direct sum of the chain complex $C_{\ast }(K^{1})$ of $K^{1}$ and the mapping cone of the filtration: $$H_{\ast }(\{K^{n}\})=H_{\ast }(C_{\ast }(K^{1})\oplus C(\{K^{n}\})).$$

The result looks very similar to the graded module representation. The advantage is that in this case the homology may still be computed over the same ring. If this ring is a field, the computations are significantly simplified.

The inclusions are still implicitly present in the chain complex.

The case of multiparameter filtration will look more complicated. Still can be computed step-by-step.