Persistent homology (an example)

Here we follow the article "Persistent homology - a Survey," by Herbert Edelsbrunner and John Harer, published in 2008 in "Surveys on discrete and computational geometry," Volume 453.

Consider the sphere, which has known homology groups. Consider a slightly bent embedding of the sphere in $\R^3$, call it $M$, as in the diagram below (imagine it as a hollow blob, whose outline is drawn below). Let $f:M\to \R$ be the height function, measuring the distance from a point in $M$ to a plane just below $M$, coming out of the page. Then we have some critical values $t_0,t_1,t_2,t_3$, as indicated below. Note we have embedded the shape so that no two critical points of $f$ have the same value.

This is remniscent of Morse theory. Set $M_i = f^{-1}[0,t_i]$ and $b_i = \dim(H_i)$ the $i$th Betti number. Then we may easily calculate the Betti numbers of the $M_j$, as in the table below.
$$\renewcommand\arraystretch{1.3} \begin{array}{r|c|c|c|c|c} & M_0 & M_1 & M_2 & M_3 & M \\\hline b_0 & 1 & 2 & 1 & 1 & 1 \\\hline b_1 & 0 & 0 & 0 & 0 & 0 \\\hline b_2 & 0 & 0 & 0 & 1 & 1 \end{array} \renewcommand\arraystretch{1}$$
Definition: In the context above, suppose that there is some $p$ and $j>i$ such that:

• $b_p(M_i)=b_p(M_{i-1})+1$,
• $b_p(M_j)=b_p(M_{j-1})-1$, and
•  the generator of $H_p$ introduced at $t_i$ is the same generator of $H_p$ that disappears at $t_j$.

Then $(i,j)$ (or ($t_i,t_j$)) is called a persistence pair and the persistence of $(i,j)$ is $j-i$ (or $f(j)-f(i)$).

For $i$ not in a persistence pair, we say that $i$ represents an essential cycle, or that the persistence of $i$ is infinite. In the example considered, the only persistence pair is $(1,2)$. This may be presented in a persistence diagram, with the indices of critical points on both axes, and the persistence measured as a vertical distance.

If we put a simplicial complex structure on $M$, we may also calculate the homology (and persistence pairs, although they may be different than the ones found above). To make calculations easier, we instead describe a CW structure on our embedded sphere $M$ (with $X_i$ the $i$-skeleton, and the ordering of the $i$-cells as indicated). The results will be the same as for a simplicial complex structure.

This gives one 0-cell, two 1-cells, and three 2-cells (with the obvious gluings), allowing us to construct the chain groups $C_p$ as well as maps between them. The map $d_p:C_p\to C_{p-1}$ as a matrix has size $\dim(C_{p-1})\times \dim(C_p)$, and has entry $(i,j)$ equal to the number of times, counting multiplicity, that the $i$th $(p-1)$-cell is a face of the $j$th $p$-cell. Calculations are done in $\Z/2\Z$.
$$d_2\ :\ C_2\to C_1 \hspace{.5cm}\text{is}\hspace{.5cm} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} \hspace{2cm} d_1\ :\ C_1\to C_0 \hspace{.5cm}\text{is}\hspace{.5cm} \begin{bmatrix} 0 & 0 \end{bmatrix}$$
The Betti numbers are then $b_p = \dim(C_p) - \text{rk}(d_p)-\text{rk}(d_{p+1})$. From above, it is immediate that $\text{rk}(d_1)=0$, $\text{rk}(d_2) = 2$, and $\text{rk}(d_p)=0$ for all other $p$. This tells us that
$$\begin{align*} b_0 & = \dim(C_0) - \text{rk}(d_0) - \text{rk}(d_1) = 1 - 0 - 0 = 1, \\ b_1 & = \dim(C_1) - \text{rk}(d_1) - \text{rk}(d_2) = 2 - 0 - 2 = 0, \\ b_2 & = \dim(C_2) - \text{rk}(d_2) - \text{rk}(d_3) = 3 - 2 - 0 = 1, \\ \end{align*}$$
as expected. To find the persistence pairs, we introduce a filtration on the simplices (equivalently, on the cells) by always having the faces of a cell precede the cell, as well as lower-dimensional cells preceding higher-dimensional cells. Using the same ordering as described above, consider the following filtration:
$$\begin{align*} K_0 & = \{\}, \\ K_1 & = \{e^0_1\}, \\ K_2 & = \{e^0_1,e^1_1,e^1_2\} ,\\ K_3 & = \{e^0_1,e^1_1,e^1_2,e^2_1,e^2_2,e^2_3\}, \end{align*}$$
so $\emptyset = K_0\subset K_1\subset K_2\subset K_3 = M$. This gives an ordering on all the cells of $M$, namely
$$\sigma_1 = e^0_1,\ \sigma_2 = e^1_1,\ \sigma_3 = e^1_2,\ \sigma_4 = e^2_1,\ \sigma_5 = e^2_2,\ \sigma_6 = e^2_3.$$
Construct the boundary matrix $D$, with the $(i,j)$ entry of $D$ equal to the number of times, counting multiplicity, modulo 2, that $\sigma_i$ is a codimension 1 face of $\sigma_j$. In the case of our example sphere, we get the matrix
$$D = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \ \ \sim\ \ \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$
in its reduced form (call it $\tilde D$). With respect to the matrix $\tilde D$, define the following numbers:
$$\begin{align*} low(j) & = \text{the row number of the lowest non-zero entry in column $j$} ,\\ zero(p) & = \text{the number of zero columns that correspond to $p$-simplices} ,\\ one(p) & = \text{the number of 1s in rows that correspond to $p$-simplices}. \end{align*}$$
We calculate all the relevant values of these expressions to be as below.
$$\begin{align*} low(1) & = 0 & zero(0) & = 1 & one(0) & = 0 \\ low(2) & = 0 & zero(1) & = 2 & one(1) & = 2 \\ low(3) & = 0 & zero(2) & = 1 & one(2) & = 0 \\ low(4) & = 2 \\ low(5) & = 3 \\ low(6) & = 0 \end{align*}$$
For persistence, we have

• if $low(j)=i\neq 0$, then $(i,j)$ is a persistence pair, 
• if $low(j)=0$ and there is no $k$ such that $low(k)=j$, then $j$ is an essential cycle.

For our sphere example, we get two persistence pairs $(2,4)$ and $(3,5)$, and two essential cycles 1 and 6. Note that this is different from the persistence pairs found by the height function $f:M\to \R$ earlier (but there are still two essential cycles), because there we were comparing the homologies $H_p(M_j)$, but here we are comparing $H_p(K_\ell)$. The persistence diagram is as below.

As an added feature, from the numbers above we may calculate the homology and relative homology groups. Construct the relative chain groups $C_p(M,K_\ell) = C_p(M)/C_p(K_\ell)$ and set $zero(p,\ell)$ to be $zero(p)$ for the lower right submatrix of $\tilde D$ corresponding to the cells in $M-K_\ell$ (and similarly for $one(p,\ell)$). We find these numbers for the bent sphere to be as below.
$$\begin{align*} zero(0,0) & = 1 & zero(0,1) & = 0 & zero(0,2) & = 0 & zero(0,3) & = 0 \\ zero(1,0) & = 2 & zero(1,1) & = 2 & zero(1,2) & = 0 & zero(1,3) & = 0 \\ zero(2,0) & = 1 & zero(2,1) & = 1 & zero(2,2) & = 1 & zero(2,3) & = 0 \\[10pt] one(0,0) & = 0 & one(0,1) & = 0 & one(0,2) & = 0 & one(0,3) & = 0 \\ one(1,0) & = 2 & one(1,1) & = 2 & one(1,2) & = 0 & one(1,3) & = 0 \\ one(2,0) & = 0 & one(2,1) & = 0 & one(2,2) & = 0 & one(2,3) & = 0 \end{align*}$$
Note that $zero(p,0)=zero(p)$ and $one(p,0)=one(p)$, as well as $zero(p,3)=one(p,3)=0$. The above numbers are useful in calculating
$$\begin{align*} \dim(H_p(M)) & = zero(p)-one(p), \\ \dim(H_p(M,K_\ell)) & = zero(p,\ell) - one(p,\ell). \end{align*}$$

References: Edelsbrunner and Harer (Persistent homology - a Survey)