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 are metric spaces and is the set of all relations in such that every element in has at least one correspondent in and vice versa. Then the GH distance can be thought as

In particular we want to compute the Gromov-Hausdorff distance for finite metric spaces (and also maybe the optimal correspondence between and ). 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 to be the solution of our convex relaxation and we show that is in fact a relaxed distance: we prove it is a semi-metric by proving that it satisfies triangular inequality. If are isometric we obtain , 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 there exists a small local neighborhood where the topologies induced by and are equivalent.

A fast non-convex algorithm for matching

Computing 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 based on the Gromov-Hausdorff objective. This algorithm gives us the correspondence between the two figures in the top of this page.