Persistent Homology

Track the birth and death of topological features across scales. Learn the matrix reduction algorithm at the heart of TDA.

Tracking Features Across Scales

Persistent homology extends ordinary homology to filtrations. Instead of computing homology at a single scale, we track how topological features are born and die as we move through the filtration.

Each feature has a birth time (when it first appears) and adeath time (when it merges or fills in). The difference is thepersistence — a measure of how significant the feature is. Features with high persistence are signal; low persistence is noise.

Birth, Death, and Persistence

Birth

A feature is born when a cycle appears that wasn't a boundary at any earlier stage. For H₀, birth happens when a vertex appears (new component). For H₁, birth happens when a cycle of edges forms without bounding a triangle.

Death

A feature dies when it becomes a boundary. For H₀, death happens when an edge connects two components (they merge). For H₁, death happens when triangles fill in a loop, making it bound a surface.

persistence = death - birth
High persistence = significant feature, Low persistence = noise

Matrix Reduction Algorithm

Persistent homology is computed by reducing the boundary matrix using column operations. Step through the algorithm to see how birth-death pairs are extracted from the reduced matrix.

Step 1 / 0

Algorithm Overview
  1. Build boundary matrix from filtration
  2. Process columns left to right
  3. For each column, find lowest 1 (the "low" index)
  4. If another column has same low, add them (mod 2)
  5. When low is unique, record birth-death pair
Key Insight

When an edge "kills" a component (connects two pieces), we pair the edge with the vertex that was born earlier. The persistence is death - birth.

The Standard Algorithm

The algorithm processes the boundary matrix column by column, reducing it to a form where birth-death pairs can be read off directly.

  1. Build boundary matrix D — columns are simplices in filtration order; entry D[i,j] = 1 if simplex i is in the boundary of simplex j.
  2. Process columns left to right — for each column j, find the lowest row with a 1 (the "low" of column j).
  3. Reduce — if another column i has the same low, add column i to column j (mod 2). Repeat until the low is unique or the column is zero.
  4. Extract pairs — if low(j) = i and column j is non-zero, then (simplex i, simplex j) is a birth-death pair.
Time complexity: O(n³) where n = number of simplices
Space: O(n²) for the boundary matrix

The Elder Rule

When two components merge in H₀, which one "survives" and which one "dies"? The elder rule says the older component (born earlier) survives, and the younger one dies at the merge time.

Example

Suppose vertex v₀ is born at ε=0, vertex v₃ is born at ε=0, and edge (v₀, v₃) appears at ε=0.5. The two components merge. Since both were born at the same time, one arbitrarily survives (say v₀), and v₃ dies at ε=0.5. This creates the pair (birth=0, death=0.5).

Essential Features

Some features never die — they persist to infinity. These are calledessential features and represent the homology of the full complex at the end of the filtration.

Essential H₀

At least one connected component survives forever — the final complex is connected. If there are multiple essential H₀ classes, the final complex has multiple components.

Essential H₁

An essential loop never gets filled in by triangles. This happens when the underlying space has a genuine 1-dimensional hole (like a torus or annulus).

Key Takeaways

  • Birth — when a feature first appears in the filtration
  • Death — when a feature becomes a boundary (merges or fills in)
  • Persistence = death - birth — measures significance
  • Matrix reduction — O(n³) algorithm to compute all pairs
  • Essential features — never die, persist to infinity