Ultrametric Gromov-Hausdorff and Gromov-Wasserstein Distances

The Gromov-Hausdorff (GH) distance provides a flexible notion of dissimilarity between datasets. It is known that computing the GH distance between finite metric spaces leads to NP-Hard computational problems. This is true even for finite ultrametric spaces, which are highly structured metric spaces satisfying the so-called 'strong' triangle inequality. We identify a one-parameter family of Gromov-Hausdorff-like distances dGH_p between finite metric spaces, for p \in [1,\infty], with the property that dGH_1 is the standard GH distance (and therefore NP-hard to compute) whereas, surprisingly, the case p=\infty yields a notion of distance  between ultrametric spaces which is computable in polynomial time on the cardinality of the inputs. This distance is itself an ultrametric on the collection of all ultrametric spaces.  Ultrametric spaces are widespread in applications and are, in particular, the standard output type of hierarchical clustering algorithms (in the form of dendrograms).

This talk will overview these and related results and will also describe an analogous construction based on optimal transport which leads to interesting computational alternatives.

Facundo Mémoli is a professor in the Department of Mathematics and in the Department of Computer Science and Engineering at the Ohio State University. Facundo obtained his PhD at the University of Minnesota in 2005, he was then a postdoc at Stanford, and joined OSU as a faculty in 2013. His research interests include topics in the intersection of metric geometry, topology, optimal transport, and applications to science and engineering such as topological data analysis, and networks.