Theory

Gromov-Hausdorff distance

Hausdorff distance

Suppose $A$ and $B$ are subsets of a metric space $(X,d)$.

The Hausdorff distance is:

$$d_H(A,B)=\max (\underset{x\in A}{\sup }d(x,B),\underset{y\in B}{\sup }d(A,y))$$

Here:

• $d(x,B)=\underset{y\in B}{\inf }d(x,y)$ smallest distance $x$ to $B$
• $d(A,y)=\underset{x\in A}{\inf }d(x,y)$ smallest distance $y$ to $A$

Therefore:

• $\underset{x\in A}{\sup }d(x,B)$ within $A$, how far away can you get from $B$?
• $\underset{y\in B}{\sup }d(A,y)$ within $B$, how far away can you get from $A$?

Gromov-Hausdorff distance

Suppose $A$ and $B$ are compact metric spaces and $(X,d)$ is some fixed compact metric space.

The Gromov-Hausdorff (GH) distance is:

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

where $f$, $g$ are isometric embeddings of $A$, $B$ into $X$.

Notice that this definition is relative to $(X,d)$.

Dendrogram

Persistent homology describes the clustering of point-cloud data.

The GH distance frequently serves as a pure math benchmark. Given finite sets of points $P,Q\subset {\mathbb{R}}^d$, the distance $d_{GH}(P,Q)$ is a measure of similarity of the shape of the point clouds $P$ and $Q$.

The GH distance cannot be computed efficiently (if at all), so other measures of similarity for point clouds are useful.

Desiderata for measures of point-cloud similarity:

• Quantifies topological and geometric features
• Distinguishes features from noise
• Is computable
• Recognizes when features are close in the GH metric

---

Suppose we have a finite set of points $P\subset X$ for a metric space $(X,d)$.

Fix $r\in {\mathbb{R}}_{\ge 0}$. Define a relation $x_1{\sim }_r{x}_2$ when $d(x_1,x_2)\le r$.

Let ${\simeq }_r$ be the transitive closure of ${\sim }_r$. This is an equivalence relation (generated by ${\sim }_r$) which partitions $P$ into equivalence classes. Members of each equivalence class can be obtained from one another by a sequence of “hops” between points no more than $r$ apart.

Draw a tree diagram with a junction at each $r$ where distinct clusters are joined:

Filtrations

Filtered simplicial complex

A filtered simplicial complex is a complex $\mathcal{K}$ with a collection:

$$\varnothing \subset {\mathcal{K}}_{a_1}\subset {\mathcal{K}}_{a_2}\subset \cdots \subset {\mathcal{K}}_{a_n}=\mathcal{K}$$

where each ${\mathcal{K}}_{a_i}$ is a simplicial complex which is a subcomplex of ${\mathcal{K}}_{a_{i+1}}$.

(The vertices and simplices of a subcomplex must be vertices and simplices in the supercomplex.)

Filtered space

A filtered topological space is a collection $X_t$ of spaces indexed by $t\in [0,\infty ]$ with continuous maps:

$$f_{s,t}:X_s\to X_t\text{each }s\le t$$

and these maps satisfy a transitivity compatibility:

$$X_r\stackrel{f_{r,s}}{⟶}{X}_s\stackrel{f_{s,t}}{⟶}{X}_t{f}_{r,t}=f_{s,t}\circ f_{r,s}$$

It is sometimes convenient, if a little ungainly, to consider a filtered simplicial complex as a filtered space where ${\mathcal{K}}_s$ is a simplicial subcomplex of ${\mathcal{K}}_t$ whenever $s\le t$. Such a filtered space changes only at discrete values of $t$.

Vietoris-Rips complex

Vietoris-Rips complex

Let $\mathcal{P}=\{p_1,\dots ,p_n\}$ be a finite set of points in a metric space $(X,d)$.

The Vietoris-Rips complex $\mathrm{VR}(\mathcal{P},r)$ is the complex whose vertices are the points $\mathcal{P}$, and whose $k$-simplices are those subsets $\sigma \subset \mathcal{P}$ with $k+1$ points all of which are pairwise less than $2r$ apart:

$$\begin{array}{rl}& [p_{i_0},\dots ,p_{i_k}]\\ & \text{k-simplex}\in \mathcal{P}\end{array}⟷\begin{array}{rl}& d(p_j,p_{\ell })<2r\\ & \forall j,\ell \in \{i_0,\dots ,i_k\}\end{array}$$

The VR complex is a filtered space (filtered complex) because:

$$\mathrm{VR}(\mathcal{P},r)\subset \mathrm{VR}(\mathcal{P},s)\subset \mathrm{VR}(\mathcal{P},t)\text{when}r\le s\le t$$

Notice that the VR complex and the Čech complex include the same 1-simplices: a simplex $\sigma =[p_i,p_j]$ is in the VR complex if $d(p_i,p_j)<2r$, and in the Čech complex if $B_r(p_i)\cap B_r(p_j)\ne \varnothing$. These conditions are equivalent, at least in ${\mathbb{R}}^d$.

Pairwise vs. mutual intersection

• The VR complex includes simplices for points which pairwise intersect.
• The Čech complex includes simplices for points which mutually intersect.

For example:

The three blue circles all intersect pairwise, so $[p_1,p_2,p_3]$ is in the VR complex, but they don’t mutually intersect so this simplex is not in the Čech complex.

On the other hand, the four green circles do not intersect pairwise. The VR complex and the Čech complex are the same in this case.

VR complex computability

Since the VR complex depends only on the data of pairwise distances between points, it is very easy to compute.

---

Čech and VR containments

For any point cloud $\mathcal{P}\subset {\mathbb{R}}^d$, we have:

1. $\check{\mathrm{C}}\mathrm{ech}(\mathcal{P},r)\subset \mathrm{VR}(\mathcal{P},r)$ inclusion as subcomplex
2. $\mathrm{VR}(\mathcal{P},r)\subset \check{\mathrm{C}}\mathrm{ech}(\mathcal{P},2r)$ inclusion as subcomplex

The first is true because any mutual intersection implies the pairwise intersections.

The second is true because any pairwise intersection of $B_r$ balls implies that the $B_{2r}$ balls extend to cover other centers. So the centers of all points are in the $2r$-balls of each of the others, thus the centers are in the mutual intersection.

Persistent homology, barcodes

Persistent homology

Let ${\mathcal{K}}_t$ be a filtered simplicial complex.

Fix $k\in \mathbb{N}$. For any $t\in [0,\infty )$, define:

$$V_k^t=H_k({\mathcal{K}}_t;\mathbb{R})$$

Whenever $s\le t$ there is a map ${\mathcal{K}}_s\to {\mathcal{K}}_t$ and this induces linear maps on homology:

$$L_k^{s,t}:V_k^s\to V_k^t$$

These satisfy $L_k^{r,t}=L_k^{s,t}\circ L_k^{r,s}$.

The persistent homology of ${\mathcal{K}}_t$ is the collection of vector spaces $V_k^t$ and linear maps $L_k^{s,t}$.

Persistent homology is defined for any filtered simplicial complex. For example, we can take persistent homology of the Čech complex or of the Vietoris-Rips complex.

Persistent VR homology - Structure Theorem

Let $V_k^r=H_k(\mathrm{VR}(\mathcal{P},r))$ for $r\in [0,\infty )$ be the persistent homology of the VR complex of a point cloud $\mathcal{P}$.

Fix $k\in \mathbb{N}$. Then $\{V_k^r{\}}_{r\in {\mathbb{R}}^{>0}}$ has a canonical decomposition as a direct sum of persistence intervals:

$$\{V_k^r{\}}_{r\in {\mathbb{R}}^{>0}}\stackrel{\sim }{⟶}\underset{i}{⨁}\mathrm{P}(a_i,b_i)$$

Persistence interval

For any $a<b$ with $a\in [0,\infty )$ and $b\in [0,\infty ]$, define:

$$\mathrm{P}(a,b{)}_r=\{\begin{array}{ll}\mathbb{R}& r\in [a,b)\\ \{0\}& r\notin [a,b)\end{array}$$

with (linear) filtration maps $L^{r,s}:\mathrm{P}(a,b{)}_r\to \mathrm{P}(a,b{)}_s$ given by $L^{r,s}={\mathrm{Id}}_{\mathbb{R}}$ when $r,s\in [a,b)$.

Illustration - barcode and persistence diagrams

Barcode diagram:

• Each $\mathrm{P}(a_i,b_i)$ receives a horizontal bar starting at $a_i$, ending at $b_i$.
• Bar colored according to degree $k$ in $H_k(\mathrm{VR}(\mathcal{P},r))$

Persistence diagram:

• Each $\mathrm{P}(a_i,b_i)$ receives a dot placed at $(a_i,b_i)$
• Horizontal ‘birth’ axis, vertical ‘death’ axis
• Dots colored according to degree $k$ in $H_k(\mathrm{VR}(\mathcal{P},r))$

Barcode basis

We would like to understand the direct sum decompositions like the one in the example of the point cloud square:

$$H_0(\mathrm{VR}(\mathcal{P}),r)\stackrel{\sim }{⟶}{\oplus }^3\mathrm{P}(0,d/2)\oplus \mathrm{P}(0,\infty )$$

Understanding such a decomposition amounts to determining a basis of homology classes that have lifespans described by the persistence intervals.

We have:

$$H_0(\mathrm{VR}(\mathcal{P},r_2))\cong \frac{\ker ({\partial }_0)}{\mathrm{im}({\partial }_1)}\gg \gg \frac{{\mathbb{R}}^2}{\mathbb{R}}$$

A basis for $H_0$ is the equivalence class of all vectors in ${\mathbb{R}}^2$ which are not in the span $⟨v_2-v_1⟩$. For example, $v_1$ or $v_2$ or $v_1+v_2$.

Barcode diagram for $H_0$:

---

Now consider $H_1$. Cycles in $H_1$ are generated by 1-simplices which are sets of two points that are $\le 2r$ apart.

Consider again the square point cloud:

For $r<\frac{d}{2}$, we have $\mathrm{VR}(\mathcal{P},r)=\text{4 discrete points}$.

For $r=\frac{d}{2}+\epsilon$, we have $\mathrm{VR}(\mathcal{P},r)=\text{square}\simeq {\mathbb{S}}^1$.

For $r=\frac{d}{2}\sqrt{2}$, we have 4 additional 2-simplices (all combinations of 3 points).

The square will the boundary of the difference of two of the 2-simplices (complementary triangles), so the homology class of the square vanishes when $r$ reaches $\frac{d}{2}\sqrt{2}$.

Barcode diagram for $H_1$:

---

Thus:

$$\begin{array}{rl}{H}_0& \cong \mathrm{P}(0,1{)}^{\oplus 3}\oplus \mathrm{P}(0,\infty )\\ & \\ H_1& \cong \mathrm{P}\left(\frac{d}{2},\frac{d}{2}\sqrt{2}\right)\end{array}$$