Theory

Bottleneck distance

The bottleneck distance is a metric on barcode diagrams. The bars in one barcode are matched against the bars in the other. The distance between barcodes is the worst discrepancy between bars in the optimal matching.

Suppose we are given two barcode diagrams. These are two finite collections of intervals:

$$\begin{array}{c}\mathbb{I}=\{I_a{\}}_{a\in A},\mathbb{J}=\{J_b{\}}_{b\in B}(A,B\text{ finite})\\ \\ I_a=[x_a,y_a),J_b=[x_b,y_b)\end{array}$$

Now define the $d_{\infty }$-distance between two intervals by:

$$d_{\infty }(I_a,J_b)=\max (|x_b-x_a|,|y_b-y_a|)$$

Also, define:

$$\lambda (I_a)=d_{\infty }(I_a,\varnothing )=\frac{|y_a-x_a|}{2}$$

This is the $d_{\infty }$-distance to the nearest point-interval $(x,x)$.

Now, suppose we are given subsets $A^{\prime }\subset A$ and $B^{\prime }\subset B$ along with a choice of bijection $\theta :A^{\prime }\to B^{\prime }$. Define the penalty of $\theta$ to be:

$$P_{\infty ;A^{\prime },B^{\prime },\theta }=\max \left(\begin{array}{rl}& {\max }_{a\in A^{\prime }}{d}_{\infty }(I_a,J_{\theta (a)})\\ & {\max }_{a\in A\backslash A^{\prime }}\lambda (I_a)\\ & {\max }_{b\in B\backslash B^{\prime }}\lambda (J_b)\end{array}\right)$$

Bottleneck distance

The bottleneck distance from $\mathbb{I}$ to $\mathbb{J}$ is:

$$d_{\infty }(\mathbb{I},\mathbb{J})=\underset{\begin{array}{c}{A}^{\prime }\subset A\\ B^{\prime }\subset B\\ \theta :A^{\prime }\to B^{\prime }\end{array}}{\min }{P}_{\infty ;A^{\prime },B^{\prime },\theta }$$

Bars far from the diagonal are matched to the closest bars (using the ${\ell }_{\infty }$-norm whose unit balls are squares). Bars near the diagonal can be matched to the closest diagonal point. The distance to the closest point on the diagonal is $\lambda (I_a)$.

Stability Theorem: Bottleneck Distance

Let $\mathcal{P}$ and $\mathcal{Q}$ be two finite metric spaces. Fix $k\in {\mathbb{Z}}_{\ge 0}$. Let $B_{\mathcal{P}}$ be the barcode diagram for $H_k(\mathrm{VR}(\mathcal{P},\mathrm{r}))$ and let $B_{\mathcal{Q}}$ be the barcode diagram for $H_k(\mathrm{VR}(\mathcal{Q},r))$. Then:

$$d_{\infty }(B_{\mathcal{P}},B_{\mathcal{Q}})\le d_{GH}(\mathcal{P},\mathcal{Q})$$

This theorem is a kind of “stability” result regarding barcode diagrams, since it says that when two data sets $\mathcal{P}$ and $\mathcal{Q}$ are close together (measured using the ideal, if not computable, metric $d_{GH}$), then the barcode diagrams are also close together. Barcode diagrams cannot jump apart without the data sets jumping apart.

For example, if $\mathcal{P}$ is a “noisy” version of $\mathcal{Q}$, then we expect $d_{GH}(\mathcal{P},\mathcal{Q})$ to be small, and therefore the barcode diagrams should be close. Conversely, if barcode diagrams are far, the data sets differ by “more than noise.”

Wasserstein metrics

The Wasserstein metrics generalize the bottleneck metric. Instead of taking the worst discrepancy between two bars in the best matching, it uses a $p$-sum of the discrepancies of all bars in the best matching.

First define the $p$-penalty for a partial matching $\theta :A^{\prime }\to B^{\prime }$ as follows:

$$P_{p;A^{\prime },B^{\prime },\theta }={\left(\sum _{a\in A^{\prime }}{d}_{\infty }(I_a,J_{\theta (a)}{)}^p+\sum _{a\in A\backslash A^{\prime }}\lambda (I_a{)}^p+\sum _{b\in B\backslash B^{\prime }}\lambda (J_b{)}^p\right)}^{1/p}$$

Then we minimize the penalty (find the best matching):

$$d_p(\mathbb{I},\mathbb{J})=\underset{\begin{array}{c}{A}^{\prime }\subset A\\ B^{\prime }\subset B\\ \theta :A^{\prime }\to B^{\prime }\end{array}}{\min }{P}_{p;A^{\prime },B^{\prime },\theta }$$

Remark

We can recast the $p$-penalty in a more uniform symbolism by supplementing $A$ or $B$ with empty bars so that each has the same number of “bars,” and recalling the convention that $d_{\infty }(I_a,\varnothing )=\lambda (I_a)$. Then we have:

$$d_p(\mathbb{I},\mathbb{J})=\underset{\theta :A\to B}{\min }{\left(\sum _{a\in A}(||a-\theta (a)|{|}_{\infty }{)}^p\right)}^{1/p}$$