Gromov-Hausdorff and matching

This post is about this paper with Afonso Bandeira, Andrew Blumberg and Rachel Ward.

Relaxations of the Gromov-Hausdorff distance

The Gromov-Hausdorff distance is defined on the set of compact metric spaces. It measures how far two metric spaces are from being isometric. Say $X,Y$ are metric spaces and $\mathcal R$ is the set of all relations in $X\times Y$ such that every element in $X$ has at least one correspondent in $Y$ and vice versa. Then the GH distance can be thought as

$$d_{GH}(X,Y)=\min_{R\in \mathcal R} \max_{(x,y),(x',y')\in R} |d_X(x,x')-d_Y(y,y')|$$

In particular we want to compute the Gromov-Hausdorff distance for $X,Y$ finite metric spaces (and also maybe the optimal correspondence between $X$ and $Y$). But unfortunately the GH distance is NP-hard, so we do the same thing we do every night and consider a convex relaxation (in particular an SDP).

We define $\tilde d_{GH}$ to be the solution of our convex relaxation and we show that $\tilde d_{GH}$ is in fact a relaxed distance: we prove it is a semi-metric by proving that it satisfies triangular inequality. If $X, Y$ are isometric we obtain $\tilde d_{GH}(X,Y)=0$, but the converse is not true because the graph isomorphism problem can be reduced to decide whether the GH distance between two spaces is zero (and the graph isomorphism is known not to be solvable by semidefinite programs).

We study the topological properties of our relaxed distance (like convergence and compactness) and we observe that for almost every space $X$ there exists a small local neighborhood where the topologies induced by $\tilde d_{GH}$ and $d_{GH}$ are equivalent.

A fast non-convex algorithm for matching

Computing $\tilde d_{GH}$ involves solving a large SDP with non-negative constraints, which is very discouraging for now. So we propose a simple and faster non-convex algorithm to address the matching problem between $X,Y$ based on the Gromov-Hausdorff objective. This algorithm gives us the correspondence between the two figures in the top of this page.