webinar register page

IMA Data Science Seminar - Facundo Mémoli
Speaker: Facundo Mémoli
Title: ltrametric Gromov-Hausdorff and Gromov-Wasserstein Distances
Abstract: 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.

Feb 23, 2021 01:25 PM in Central Time (US and Canada)

Webinar is over, you cannot register now. If you have any questions, please contact Webinar host: Georgia M Kroll.