The surprising reasonableness of the earth movers distance in high dimensions

The earth mover’s distance (EMD) is a scalar measure of dissimilarity between histograms.  Introduced over 200 years ago, the EMD has played a central role in linear programming, information retrieval, and is emerging as useful objective in machine learning.  During the 1990’s, the EMD was generalized from a functional that acts on pairs of histograms to to $d>2$ histograms, and the technique that accomplishes this recasts the EMD as a particular kind of linear program.  In this talk, I will describe a recent result that shows that the optimal value of this linear program possesses geometrically interesting properties, including Minkowski additivity and convex monotonicity. These properties lead to a vast generalization of the EMD, and also provide us with new capabilities, including the ability to rapidly and exactly solve linear programs that, for lack of atoms on earth, could otherwise not be solved.  This work arose within the context of Internet traffic anomaly detection, and I will discuss this as well  https://doi.org/10.1016/j.dam.2019.02.042

For this talk, my affiliation will be with American Family Insurance.