Some recent developments in the use of Gromov-Hausdorff and<br/><br/>Gromov-Wasserstein metrics

Monday, October 5, 2009 - 1:15pm - 2:00pm
Lind 305
Facundo Mémoli (Stanford University)
Keywords: Gromov-Hausdorff distance,
Gromov-Wasserstein distance, shape analysis, metric geometry

Abstract: The Gromov-Hausdorff distance provides a powerful tool for formalizing
the problem of shape matching. Two problems with it are that (1) in
practice it leads to combinatorial optimization problems which are NP
hard and (2) despite its theoretical attractiveness and naturality,
it has been difficult to use for studying and establishing links to
the many other shape matching methods available in the literature. The
Gromov-Wasserstein distance, a variant of the Gromov-Hausdorff
distance that is based on mass transportation ideas, directly leads to
continuous optimization problems with quadratic objective functions
and linear constraints. Furthermore, it has been proved that the
methods based on shape distributions, shape context/integral
invariants, and eccentricity can all be related to this
Gromov-Wasserstein distance via explicit lower bounds. In this talk we
review the construction of the GW distance, its properties and lower
bounds. In particular, we describe recent work done on (1) relating it
to persistent topology based shape signatures, and (2) on defining a
certain spectral notion of the GW distance. This spectral notion of
the GW distance permits proving that several invariants constructed
from the spectrum of the Laplace-Beltrami operator on manifolds are
stable in a quantitative way.
MSC Code: