Metric Geometry in Shape Matching

The problem of object matching under invariances can be studied using certain tools from Metric Geometry. The central 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 by the choice of the metrics with which one 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. I will discuss different adaptations of these ideas, and in particular will show a construction of an L^p version of the Gromov-Hausdorff metric called Gromov-Wassestein distance which is based on mass transportation ideas. This new metric leads directly to quadratic optimization problems on continuous variables with linear constraints. As a consequence of establishing several lower bounds, it turns out that several invariants of metric measure spaces are quantitatively stable in the GW sense. These invariants provide practical tools for the discrimination of shapes and connect the GW ideas to several pre-existsting approaches.

Dr. Facundo Memoli

Postdoctoral Fellow, Mathematics Department, Stanford University on September 17, 2010 at 8:00 AM in Engineering Building III, Room 2213

Facundo Memoli is a postdoctoral fellow in the Mathematics Department at Stanford University. His research interests are in shape and data analysis and in metric geometry. Facundo received his B.Sc. and M.Sc. in Electrical Engineering from the Universidad de la Republica in Uruguay, and his Ph.D. in Electrical Engineering from the University of Minnesota.

The Department of Electrical and Computer Engineering hosts a regularly scheduled seminar series with preeminent and leading reseachers in the US and the world, to help promote North Carolina as a center of innovation and knowledge and to ensure safeguarding its place of leading research.