The Earth Mover's Distance Through the Lens of Algebraic Combinatorics

Abstract

The earth mover's distance (EMD) is a metric for comparing two histograms, with burgeoning applications in image retrieval, computer vision, optimal transport, physics, cosmology, political science, epidemiology, and many other fields. In this thesis, however, we approach the EMD from three distinct viewpoints in algebraic combinatorics. First, by regarding the EMD as the symmetric difference of two Young diagrams, we use combinatorial arguments to answer statistical questions about histogram pairs. Second, we adopt as a natural model for the EMD a certain infinite-dimensional module, known as the first Wallach representation of the Lie algebra su(p,q), which arises in the Howe duality setting in Type A; in this setting, we show how the second fundamental theorem of invariant theory generalizes the "northwest corner rule'' from optimal transport theory, yielding a simple interpretation of the "partial matching'' case of the EMD via separation into invariants and harmonics. Third, we reapproach partial matching in the context of crystal bases of Types A, B, and C, which leads us to introduce a variation of the EMD in terms of distance on a crystal graph. Having exploited these three approaches, we generalize all of our EMD results to an arbitrary number of histograms rather than only two at a time. In the final chapter, we observe a combinatorial connection between generalized BGG resolutions arising in Type-A Howe duality and certain non-holomorphic discrete series representations of the group SU(p,q).