CMU Campus
Center for                           Nonlinear Analysis
CNA Home People Seminars Publications Workshops and Conferences CNA Working Groups CNA Comments Form Summer Schools Summer Undergraduate Institute PIRE Cooperation Graduate Topics Courses SIAM Chapter Seminar Positions Contact
CNA Seminar/Colloquium/Joint Pitt-CNA Colloquium
Facundo Memoli
Title: The Gromov-Wasserstein distance and object matching

Abstract: The problem of object matching under invariances can be studied using certain tools from Metric Geometry. The main idea is to regard objects as metric spaces (or metric measure spaces). The type of invariance one wishes to have in the matching is encoded in the choice of the metrics with which we endow the objects. The standard example is matching objects in Euclidean space under rigid isometries: in this situation one would endow the objects with the Euclidean metric. More general scenarios are possible in which the desired invariance cannot be reflected by the preservation of an ambient space metric. Several ideas due to M. Gromov are useful for approaching this problem. The Gromov-Hausdorff distance is a natural first candidate for doing this. However, this metric leads to very hard combinatorial optimization problems and it is difficult to relate to previously reported practical approaches to the problem of object matching. We discuss different adaptations of these ideas, and in particu- lar we construct an Lp version of the Gromov-Hausdorff metric called Gromov-Wassestein distance using mass transportation ideas. This new metric leads directly to quadratic optimization problems on con- tinuous variables with linear constraints. We identify several invariants of metric measure spaces that are quantitatively stable in the GW sense. These invariants provide prac- tical tools for the discrimination of shapes.

Date: Tuesday, October 12, 2010
Time: 1:30 pm
Location: Wean Hall 8220
Submitted by:  Dejan Slepcev