2024-04-16

Gromov-Hausdorff Distance

Summary of notes on the Hausdorff and Gromov-Hausdorff distance (see https://www2.math.upenn.edu/~brweber/Lectures/USTC2011/Lecture%205%20-%20Gromov-Hausdorff%20distance.pdf)

Let $A$ be a set in a metric space $X$ and $r>0$. The r-thickening or r-neighborhood of $A$ is given by the cover of balls centered at each point of $A$ with radius $r$, i.e.,

$$A^{(r)}=\bigcup _{x\in A}{B}_x(r).$$

Hausdorff distance

For closed sets $A,B$ in $X$, we define the Hausdorff distance by

$$d_H(A,B)=\inf \{r>0\mid B\subset A^{(r)}\text{ and }A\subset B^{(r)}\},$$

One may show that $d_H(A,B)$ is the farthest distance any point of $B$ is from $A$, or the farthest distance any point of $A$ is from $B$ (take the larger one). Moreover, the set of closed sets in $X$ with $d_H$ forms a metric.

Note that if $X$ is not bounded, there may be closed sets $A$ and $B$ with $d_H(A,B)=\infty$.

The Gromov-Hausdorff distance generalizes the Hausdorff distance.

Gromov-Hausdorff distance

Given two closed metric spaces $A$ and $B$, the Gromov-Hausdorff distance is given by

$$d_{GH}(A,B)=\underset{f,g}{\inf }{d}_H(f_{A\to X}(A),f_{B\to X}(B))$$

where $f_{A\to X}$ denotes an isometric embedding of $A$ into some metric space $X$. The infimum is taken over all such embeddings.

In other words, we embed the two metric spaces $A$ and $B$ into some larger metric space $X$ and find the Hausdorff distance. We then take the smallest value given across all possible embeddings.

Bottleneck Distance

Recall that a persistence diagram is simply a set of points in ${\mathbb{R}}^2$. Let $X$ and $Y$ be two such persistence diagrams. We want to define a distance between the two diagrams. If $X$ and $Y$ have the same cardinality, we can find bijections $\eta :X\to Y$ between the two. For each bijection we find the supremum of distances between a point in $X$ and its corresponding point in $Y$. We then want to the tahe smallest distance found. That is,

Bottleneck Distance

The bottleneck distance between two persistence diagrams is given by

$$W_{\infty }(X,Y)=\underset{\eta :X\to Y}{\inf }\underset{x\in X}{\sup }\Vert x-\eta (x){\Vert }_{\infty }.$$

One may easily see that $W_{\infty }$ is a metric.