Lecture 6: Persistence#

  • As in the previous notebooks, plotting and example data are in a separate python file: lecture6_helpers.py.

  • There is one exercise, followed by a cell with its hidden solution. Everything else is already written: read it, run it, and play with the examples.

import numpy as np
import matplotlib.pyplot as plt
import gudhi

from lecture6_helpers import (
    letter2int, int2letter,             # 'A' -> 0 and 0 -> 'A': SimplexTree vertices are integers
    SLIDE_COORDS, plot_filtration,      # Sec. 1: where to draw A, B, C, D, and a picture of a filtration
    show_table,                         # Sec. 1: a table of beta^{i,j} or mu^{i,j}
    CLOUDS,                             # Sec. 2: some point clouds
    LETTERS, plot_radii,                # Sec. 3: the letters of Lecture 4, and their complexes at a few radii
)
plt.rcParams["figure.dpi"] = 110

1. From persistent Betti numbers to the diagram#

The running example from the lecture: four vertices and four edges, added one at a time.

example = gudhi.SimplexTree()
example.insert([letter2int("A")], filtration=1)
example.insert([letter2int("B")], filtration=2)
example.insert([letter2int("A"), letter2int("B")], filtration=3)
example.insert([letter2int("C")], filtration=4)
example.insert([letter2int("D")], filtration=5)
example.insert([letter2int("A"), letter2int("C")], filtration=6)
example.insert([letter2int("B"), letter2int("C")], filtration=7)
example.insert([letter2int("B"), letter2int("D")], filtration=8)
plot_filtration(example, SLIDE_COORDS)

The persistent Betti number \(\beta_0^{i,j} = \operatorname{rank}\big(H_0(K_i) \to H_0(K_j)\big)\) counts the components born at or before \(K_i\) that are still alive in \(K_j\). GUDHI computes it with persistent_betti_numbers(i, j). The table is laid out as in the lecture: one column per \(i\) and one row per \(j\), with \(j\) growing upwards. Compare it with your answer from the lecture:

n = 8      # K_1, ..., K_8
p = 0      # the dimension: 0 for components, 1 for loops

# GUDHI needs compute_persistence before persistent_betti_numbers. By default it skips the homology of
# the top dimension of the complex (here 1: there are edges but no triangles), so it would miss the loop
# ABC. persistence_dim_max=True makes it compute that dimension too.
example.compute_persistence(persistence_dim_max=True)


def beta(i: int, j: int) -> int:
    # beta_p^{i,j}: the classes born at or before K_i that are still alive in K_j
    if i == 0 or j == n + 1:     # K_0 is empty, and the 0 vector space is attached at the end, as K_{n+1}
        return 0
    return example.persistent_betti_numbers(i, j)[p]     # [p]: the dimension we want


show_table(beta, n, f"beta_{p}^{{i,j}}")

Reading a column. Column \(i\) is what happens from step \(i\) of the filtration onwards: read it from the bottom up. In column 2, at \((2, 2)\) we have 2: \(K_2\) has \(A\) and \(B\), two isolated vertices. At \((2, 3)\) the edge \(AB\) comes in and connects them, so \(\beta_0^{2,3}\) becomes 1, and it stays 1 all the way up the column. Look at the other columns, and make sure you understand every number.

Your turn: think about what the table looks like for \(\beta_1^{i,j}\), the loops. Write it on paper, and then change the cell above to check your answer: you only have to edit one line! (Set it back to p = 0 before going on.)

Exercise 1.1: mu(i, j)#

\(\mu_0^{i,j}\) counts the classes born at \(K_i\) that die entering \(K_j\):

\[\mu_0^{i,j} = \big(\beta_0^{i,j-1} - \beta_0^{i,j}\big) - \big(\beta_0^{i-1,j-1} - \beta_0^{i-1,j}\big), \qquad 0 < i < j \le n + 1.\]

The first bracket counts the classes born at or before \(i\) that die entering \(j\), and the second one removes those born at or before \(i - 1\). For \(j = n + 1\) it counts the classes that never die, since beta(i, n + 1) is 0.

Your turn: write mu(i, j) with this formula.

TIP: Use the formula above and calls to the function beta from the last code cell (remember to set the cell back to its original form, and rerun it if you had edited it)

def mu(i: int, j: int) -> int:
    raise NotImplementedError

Solution hidden in this cell#

Now let’s visualize the table for the values of \(\mu\) and also the persistence diagram. We plot the diagram resulting from your table and compare it to the one that GHUDI provides, so that you can learn how to build and plot diagrams with the library.

show_table(mu, n, "mu_0^{i,j}", strict=True, infinity=True)

my_diagram = []
for i in range(1, n + 1):
    for j in range(i + 1, n + 2):
        death = j
        if j == n + 1:
            death = float("inf")                 # a_{n+1} = infinity
        for k in range(mu(i, j)):                # mu counts the classes: one point for each
            my_diagram.append((0, (i, death)))   # GUDHI's format: (dimension, (birth, death))

fig, axes = plt.subplots(1, 2, figsize=(10, 4.5))
gudhi.plot_persistence_diagram(my_diagram, axes=axes[0])
axes[0].set_title("from your mu")
gudhi.plot_persistence_diagram(example.persistence(persistence_dim_max=True), axes=axes[1])
axes[1].set_title("GUDHI")
plt.tight_layout(); plt.show()

They agree on \(H_0\). GUDHI also finds an \(H_1\) point at \((7, \infty)\): the loop \(AB + BC + CA\), born when \(BC\) enters, and never filled, since there are no triangles.

2. Persistence diagrams of point clouds#

For a point cloud, the filtration usually comes from a growing radius in one of the point clouds complexes that we have studied (Lecture 2). Here we will use the alpha complex. Recall that at every radius it has the shape of the union of balls, like the Čech complex, and the filtration value of each simplex is the radius at which it appears. Then:

  • st.persistence() gives all the pairs (dimension, (birth, death));

  • gudhi.plot_persistence_diagram(diagram) draws them: red for \(H_0\) (components), blue for \(H_1\) (holes).

A point far from the diagonal lives long: it is a real feature. A point near the diagonal is born and dies almost at once: it is noise.

# Choose a cloud: "circle", "two circles", "figure eight", "three blobs" or "disk"
name = "circle"
points = CLOUDS[name]

# AlphaComplex builds the alpha complex of the points (Lecture 2), and create_simplex_tree turns it into a
# SimplexTree whose filtration value is the radius at which each simplex appears. By default GUDHI stores
# the squared radius instead (it is cheaper to compute); output_squared_values=False gives the radius itself.
# Any other filtration works too: another complex from GUDHI that we have seen, like
# gudhi.RipsComplex(points=points, max_edge_length=2).create_simplex_tree(max_dimension=2), one from
# the documentation, or your own, inserting simplices with their values into a SimplexTree as in Section 1.
st = gudhi.AlphaComplex(points=points).create_simplex_tree(output_squared_values=False)
diagram = st.persistence()       # all the pairs (dimension, (birth, death))

fig, axes = plt.subplots(1, 2, figsize=(10, 4.5))
axes[0].scatter(points[:, 0], points[:, 1], s=8, color="black")
axes[0].set_aspect("equal")
axes[0].set_title(name)
gudhi.plot_persistence_diagram(diagram, axes=axes[1]) # comment this line if you want to hide the diagram
plt.tight_layout(); plt.show()

Your turn: change the variable name in the cell above to some of the commented options and visualize those diagrams.

You can try to think by youself how they are going to look before plotting them (to do so comment out the diagram plot and just plot the point cloud).

3. The letter A, without guessing the radius#

In Lecture 4 Notebook (optional exercise) you sorted the letters by \((\beta_0, \beta_1)\), but the letters were given as point clouds and you had to guess a radius \(r\) allowing to extract useful information.

Below we look at three radii:

  • too small: we have a lot of “fake” connected components, and we miss the circle.

  • just right: we have only one connected component and one loop.

  • too big: the loop closes.

def classify(points: np.ndarray, r: float) -> tuple[int, int]:
    st = gudhi.AlphaComplex(points=points).create_simplex_tree(output_squared_values=False)
    st.prune_above_filtration(r)                       # keep the simplices that are there at radius r
    st.compute_persistence(persistence_dim_max=True)
    betti = st.betti_numbers()
    b0 = betti[0]
    if len(betti) > 1:
        b1 = betti[1]
    else:                                              # no edges yet: no loops
        b1 = 0
    return b0, b1


plot_radii(LETTERS["A"], [0.02, 0.12, 0.3], classify, name="A")

With the persistence diagram there is nothing to guess: it shows all the radii at once.

st = gudhi.AlphaComplex(points=LETTERS["A"]).create_simplex_tree(output_squared_values=False)
gudhi.plot_persistence_diagram(st.persistence())
plt.show()

The red point at \((0, \infty)\) is the one connected component: it is born at radius 0 and never dies. The blue point that is born between \(0\) and \(0.1\) and dies a bit after \(0.2\) is the hole of the A: any radius in between sees it. The other points are close to the diagonal: they live very briefly, so they are noise.