Barcodes & Bottleneck Distance

Overview & Motivation

The Persistent Homology article showed how to compute a persistence diagram — a multiset of birth-death pairs that summarizes the topological features of a dataset across scales. But a single diagram is just a picture. To do science, you need to compare diagrams: Is dataset A topologically similar to dataset B? Is this diagram stable under noise? Can I average over a population of diagrams?

These questions require turning the collection of all persistence diagrams into a metric space — equipping it with a notion of distance that is both mathematically well-behaved and computationally tractable. Three questions frame the challenge:

1. How do we define a “distance” between two persistence diagrams? A diagram is a multiset of points in $\mathbb{R}^2$, possibly of different sizes. Standard vector metrics don’t apply directly.
2. Why can’t we just use Hausdorff distance on the point sets? Because persistence diagrams have a special structure: short-lived features (points near the diagonal) should contribute less to the distance than long-lived ones.
3. What makes bottleneck distance the natural choice for stability, and when do you want Wasserstein instead? The answer involves a beautiful interplay between algebra (persistence modules), geometry (matchings), and analysis (stability inequalities).

The solution comes in two equivalent representations — barcodes and persistence diagrams — and two families of metrics: the bottleneck distance $d_B$, which measures the worst-case cost of matching features, and the Wasserstein distances $W_p$, which measure the total cost. Both are true metrics on the space of persistence diagrams, and both satisfy stability theorems — but with different tradeoffs.

These distances are what make TDA a statistical method rather than just a visualization trick. Without them, you can’t do hypothesis testing, confidence sets, or machine learning on topological features. They are the bridge between topology and data science.

---

Formal Framework

Barcodes as Interval Decompositions

The Persistent Homology article introduced persistence barcodes informally: each topological feature gets a bar $[b, d)$ recording when it is born and when it dies. The algebraic foundation for this representation is the Structure Theorem, which says that barcodes are not just a convenient visualization — they are a complete invariant.

Each interval module $\mathbb{I}[b_i, d_i)$ corresponds to exactly one bar in the barcode. The theorem guarantees that this decomposition is unique: different filtrations can produce different barcodes, but a given persistence module has only one barcode (up to reordering of bars).

The Space of Persistence Diagrams

To define distances between diagrams, we first need to formalize what a persistence diagram is as a mathematical object.

The diagonal plays a crucial role: it serves as a “graveyard” for unmatched features. Since two diagrams can have different numbers of off-diagonal points, we cannot match them point-to-point directly. The diagonal fixes this: any unmatched point in one diagram can be paired with a diagonal point in the other, at a cost equal to the point’s distance from the diagonal — which is exactly half its persistence, $(d - b) / 2$.

Bottleneck Distance

Geometrically, $d_B$ asks: what is the minimum cost of a perfect matching between the two diagrams, where the cost of a matching is the worst single mismatch? It is a minimax problem — minimize over matchings, maximize over points within a matching.

Wasserstein Distance

The key difference from bottleneck: Wasserstein penalizes all mismatches, not just the worst one. If two diagrams differ by many small mismatches, bottleneck says they’re close (the worst individual mismatch is small), while Wasserstein says they’re far (the total mismatch accumulates).

When to use which:

• Bottleneck ($d_B$): Stability guarantees, worst-case analysis, theoretical proofs. Bottleneck is the natural metric for the Stability Theorem because it bounds the worst individual feature displacement.
• Wasserstein ($W_1$, $W_2$): Statistical applications, persistence images, ML pipelines. $W_2$ is the standard choice in machine learning because it is sensitive to all features, not just the most persistent one. This matters when the signal is distributed across many moderate-persistence features.

The Stability Theorem

The practical utility of everything above rests on a single result: the distances we’ve defined are stable under perturbations of the input. The Persistent Homology article stated this informally; here is the full treatment.

For point cloud data, the relevant corollary translates function perturbation into geometric perturbation:

The key takeaway: stability is what makes TDA safe to use on real data. If your point cloud has measurement noise bounded by $\delta$, the persistence diagram moves by at most $2\delta$ in the bottleneck metric. Features with persistence $> 2\delta$ are guaranteed to be real topological features of the underlying space, not artifacts of noise.

The Isometry Theorem

The Stability Theorem raises a natural question: is the bottleneck distance the right metric, or just a metric? The Isometry Theorem answers this definitively.

The interleaving distance $d_I$ measures how close two persistence modules are algebraically — it is the infimum over all $\delta$ such that the modules are $\delta$-interleaved. The Isometry Theorem says that this algebraic notion of proximity is exactly captured by the geometric notion of proximity in the persistence diagram.

This is the deep reason why bottleneck distance is the canonical metric: it doesn’t just compare point sets in $\mathbb{R}^2$ — it faithfully reflects the algebraic structure of the underlying persistence modules. The Stability Theorem is then a corollary: $d_I(\mathbb{V}^f, \mathbb{V}^g) \leq \|f - g\|_\infty$ by the interleaving argument, and $d_B = d_I$ by the Isometry Theorem.

---

Visual Intuition

Bottleneck Matching

The visualization below shows two persistence diagrams (H₁ features) overlaid in a single coordinate system. Circles represent features from one dataset; diamonds represent features from another. Lines show the optimal bottleneck matching — each feature is matched to its counterpart or to the diagonal. The red line marks the bottleneck pair: the single worst-cost match that determines $d_B$.

Toggle between diagram pairs to see how different topological structures produce different matchings:

Circle vs ClusterCircle vs Figure-Eight

Bottleneck distance: d_B = 0.7050— the red line shows the worst-cost match

Circles (●) are Circle H₁ features. Diamonds (◆) are Cluster H₁ features. Dashed lines show other matches (including to diagonal).

What to notice:

1. Circle vs Cluster: The circle’s dominant loop has no counterpart in the cluster — it matches to the diagonal at a cost of half its persistence. This large diagonal match drives $d_B$.

2. Circle vs Figure-Eight: The circle’s single loop matches to one of the figure-eight’s two loops. The second figure-eight loop has no counterpart, so it too matches to the diagonal. The bottleneck distance reflects the mismatch in number of significant loops.

Stability Under Noise

Drag the σ slider to add Gaussian noise to a circle point cloud and watch the persistence diagram respond. The metrics panel confirms that the Stability Theorem’s bound $d_B \leq 2 \cdot d_H$ holds at every noise level:

Persistence Diagram

Noise σ0.10

d_B ≈ 0.1912d_H ≈ 0.28142·d_H ≈ 0.5628✓ Bound holds

Faded points = base circle. Purple = noisy version. The Stability Theorem guarantees d_B ≤ 2·d_H.

What to notice:

1. At low noise ($\sigma < 0.1$), the diagram barely moves — the topological signal is robust.
2. As noise increases, short bars (near the diagonal) appear and shift, but the dominant features maintain their persistence.
3. The bound $2 \cdot d_H$ is always above $d_B$ — often with significant slack, because the bound is worst-case.

---

Working Code

Computing and Plotting Barcodes

import numpy as np
from ripser import ripser
from persim import plot_diagrams
import matplotlib.pyplot as plt

np.random.seed(42)

# Four canonical shapes with distinct topological signatures
def sample_circle(n=150, noise=0.05):
    theta = np.random.uniform(0, 2 * np.pi, n)
    r = 1.0 + np.random.normal(0, noise, n)
    return np.column_stack([r * np.cos(theta), r * np.sin(theta)])

def sample_cluster(n=150):
    return np.random.randn(n, 2) * 0.5

def sample_figure_eight(n=200, noise=0.05):
    n_half = n // 2
    theta1 = np.random.uniform(0, 2 * np.pi, n_half)
    theta2 = np.random.uniform(0, 2 * np.pi, n - n_half)
    left = np.column_stack([-1 + np.cos(theta1), np.sin(theta1)]) + noise * np.random.randn(n_half, 2)
    right = np.column_stack([1 + np.cos(theta2), np.sin(theta2)]) + noise * np.random.randn(n - n_half, 2)
    return np.vstack([left, right])

clouds = {
    'Circle': sample_circle(),
    'Cluster': sample_cluster(),
    'Figure-Eight': sample_figure_eight(),
}

# Compute persistence and examine barcodes
for name, pts in clouds.items():
    result = ripser(pts, maxdim=1)
    dgms = result['dgms']
    for dim in range(2):
        dgm = dgms[dim]
        finite = dgm[np.isfinite(dgm[:, 1])]
        if len(finite) > 0:
            pers = finite[:, 1] - finite[:, 0]
            print(f"{name} H_{dim}: {len(finite)} finite bars, max persistence = {pers.max():.4f}")

Bottleneck Distance Computation

from persim import bottleneck

# Extract H₁ diagrams
results = {name: ripser(pts, maxdim=1) for name, pts in clouds.items()}
h1_dgms = {}
for name, result in results.items():
    dgm = result['dgms'][1]
    h1_dgms[name] = dgm[np.isfinite(dgm[:, 1])]

# Pairwise bottleneck distances
names = list(clouds.keys())
for i, a in enumerate(names):
    for j, b in enumerate(names):
        if i < j:
            if len(h1_dgms[a]) > 0 and len(h1_dgms[b]) > 0:
                d = bottleneck(h1_dgms[a], h1_dgms[b])
            else:
                nonempty = h1_dgms[a] if len(h1_dgms[a]) > 0 else h1_dgms[b]
                d = (nonempty[:, 1] - nonempty[:, 0]).max() / 2
            print(f"d_B({a}, {b}) = {d:.4f}")

# Verify triangle inequality
def safe_bottleneck(dgm_a, dgm_b):
    """Bottleneck distance handling empty diagrams."""
    if len(dgm_a) > 0 and len(dgm_b) > 0:
        return bottleneck(dgm_a, dgm_b)
    elif len(dgm_a) > 0:
        return (dgm_a[:, 1] - dgm_a[:, 0]).max() / 2
    elif len(dgm_b) > 0:
        return (dgm_b[:, 1] - dgm_b[:, 0]).max() / 2
    return 0.0

for a, b, c in [('Circle', 'Cluster', 'Figure-Eight')]:
    d_ab = safe_bottleneck(h1_dgms[a], h1_dgms[b])
    d_bc = safe_bottleneck(h1_dgms[b], h1_dgms[c])
    d_ac = safe_bottleneck(h1_dgms[a], h1_dgms[c])
    print(f"Triangle: d_B(A,C) = {d_ac:.4f} ≤ d_B(A,B) + d_B(B,C) = {d_ab + d_bc:.4f}: {d_ac <= d_ab + d_bc + 1e-10}")

Wasserstein Distance and Comparison

from gudhi.wasserstein import wasserstein_distance

# Compare bottleneck, W₁, and W₂ on the same pairs
pairs = [('Circle', 'Cluster'), ('Circle', 'Figure-Eight')]

for a, b in pairs:
    dgm_a, dgm_b = h1_dgms[a], h1_dgms[b]
    if len(dgm_a) == 0 or len(dgm_b) == 0:
        print(f"{a} vs {b}: empty diagram, skipping Wasserstein")
        continue

    d_b = bottleneck(dgm_a, dgm_b)
    w1 = wasserstein_distance(dgm_a, dgm_b, order=1)
    w2 = wasserstein_distance(dgm_a, dgm_b, order=2)

    print(f"{a} vs {b}:  d_B = {d_b:.4f},  W_1 = {w1:.4f},  W_2 = {w2:.4f}")
    # Note: d_B ≤ W_p — bottleneck is always the cheapest metric

Stability Verification Pipeline

from scipy.spatial.distance import directed_hausdorff

# Base point cloud: clean circle
base = sample_circle(150, noise=0.0)
base_dgm = ripser(base, maxdim=1)['dgms'][1]

noise_levels = [0.0, 0.05, 0.1, 0.15, 0.2, 0.3, 0.5]
n_trials = 20

print(f"{'σ':>6}  {'mean d_H':>10}  {'mean d_B':>10}  {'mean 2·d_H':>12}  {'holds':>8}")
for sigma in noise_levels:
    d_bs, d_hs = [], []
    for _ in range(n_trials):
        noisy = base + sigma * np.random.randn(*base.shape)
        d_h = max(directed_hausdorff(base, noisy)[0], directed_hausdorff(noisy, base)[0])
        noisy_dgm = ripser(noisy, maxdim=1)['dgms'][1]
        d_b = bottleneck(base_dgm, noisy_dgm) if len(noisy_dgm) > 0 else (base_dgm[:, 1] - base_dgm[:, 0]).max() / 2 if len(base_dgm) > 0 else 0
        d_bs.append(d_b)
        d_hs.append(d_h)

    mean_db, mean_dh = np.mean(d_bs), np.mean(d_hs)
    bound = 2 * mean_dh
    holds = all(db <= 2 * dh + 1e-10 for db, dh in zip(d_bs, d_hs))
    print(f"{sigma:>6.2f}  {mean_dh:>10.4f}  {mean_db:>10.4f}  {bound:>12.4f}  {'✓' if holds else '✗':>8}")

---

Connections & Applications

• Statistical TDA: Bottleneck and Wasserstein distances enable hypothesis testing on topological features. Fasy et al. (2014) construct bootstrap confidence sets for persistence diagrams: if a point in the diagram lies outside the confidence band around the diagonal, it is a statistically significant topological feature.

• Persistence landscapes (Bubenik, 2015): an alternative representation that maps a persistence diagram to a sequence of piecewise-linear functions in a Banach space. This enables standard statistical tools — means, variances, $t$-tests — to be applied directly to topological summaries.

• Optimal transport: Wasserstein distance on persistence diagrams is a special case of optimal transport between discrete measures on $\mathbb{R}^2$. This connects TDA to the rich theory of Monge-Kantorovich problems and provides access to efficient computational tools from the optimal transport literature (Kerber, Morozov & Nigmetov, 2017).

• Sheaf Theory: sheaf-theoretic generalizations of persistence provide multi-parameter extensions where barcode decomposition no longer holds — the bottleneck distance generalizes to interleaving distance in this setting, and the Isometry Theorem shows why this generalization is natural.