Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Gromov-Wasserstein distances and the metric approach to object matching
Author: Memoli, Facundo
Citation: Foundations of Computational Mathematics, 2011; 11(4):417-487
Publisher: Springer New York LLC
Issue Date: 2011
ISSN: 1615-3375
School/Discipline: School of Computer Science
Statement of
Facundo Mémoli
Abstract: This paper discusses certain modifications of the ideas concerning the Gromov–Hausdorff distance which have the goal of modeling and tackling the practical problems of object matching and comparison. Objects are viewed as metric measure spaces, and based on ideas from mass transportation, a Gromov–Wasserstein type of distance between objects is defined. This reformulation yields a distance between objects which is more amenable to practical computations but retains all the desirable theoretical underpinnings. The theoretical properties of this new notion of distance are studied, and it is established that it provides a strict metric on the collection of isomorphism classes of metric measure spaces. Furthermore, the topology generated by this metric is studied, and sufficient conditions for the pre-compactness of families of metric measure spaces are identified. A second goal of this paper is to establish links to several other practical methods proposed in the literature for comparing/matching shapes in precise terms. This is done by proving explicit lower bounds for the proposed distance that involve many of the invariants previously reported by researchers. These lower bounds can be computed in polynomial time. The numerical implementations of the ideas are discussed and computational examples are presented.
Keywords: Gromov–Hausdorff distances; Gromov–Wasserstein distances; Data analysis; Shape matching; Mass transport; Metric measure spaces
Rights: © SFoCM 2011
RMID: 0020121092
DOI: 10.1007/s10208-011-9093-5
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.