A Cayley–Menger formula for the earth mover’s simplex

Among the more famous results of antiquity is Heron’s formula for the area of a triangle $\triangle ABC$ in terms of its side lengths $a,b,c$:

where $s=(a+b+c)/2$ is the semiperimeter. Although named for Heron of Alexandria, who recorded it in his Metrica in the first century, this result was likely known much earlier, perhaps even to Archimedes.

A natural question is whether Heron’s formula generalizes to a formula for (hyper)volume in higher dimensions; the answer depends on what exactly we wish to generalize, since in the original formula (1) in two dimensions, the side lengths $a,b,c$ have both dimension 1 and codimension 1. On one hand, if we view them as having dimension 1, then the problem is to express the volume of a $d$-dimensional simplex $\Delta$ in terms of its edge lengths (i.e., the volumes of its 1-dimensional faces). The answer to this problem is the Cayley–Menger determinant below:

where $\ell_{ij}$ is the length of the edge between the $i$th and $j$th vertices (and $\ell_{i,d+1}=\ell_{d+1,i}\coloneqq 1$ for all $i\leq d$, and $\ell_{d+1,d+1}\coloneqq 0$). On the other hand, if we view the sides of a triangle as having codimension 1, then the question is whether the volume of $\Delta$ can be expressed only in terms of its “surface area” (i.e., the volumes of its facets). In this case, the answer is no, since even for the tetrahedron it is clear that the four facet areas do not determine the volume. Hence any generalization of Heron’s formula with respect to the facets must require additional information.

The problem in this paper is to find an analogue of the Cayley–Menger formula (2), in the very specific context of the earth mover’s distance (EMD). The EMD is a metric on spaces of histograms, or probability distributions, and is essentially synonymous with the 1-Wasserstein distance and the Mallows distance [Bickel]: roughly speaking, the EMD measures the minimum amount of work required to equalize two histograms, where “work” is defined by the geometry of the feature space of the histograms. Although outside the scope of the present paper, the EMD can be viewed as the solution to the transportation problem (the founding problem of optimal transport theory), and is central to a burgeoning range of important applications in mathematics, physics, and the social sciences; see Villani’s comprehensive reference [Villani] for further details.

In this paper, we consider histograms in which the bins are the integers $1,\ldots,n$ on the number line. It is natural to generalize the EMD in order to compare an arbitrary number of histograms $h_{0},\ldots,h_{d}$, rather than only two at a time: in this case, the EMD measures the minimum amount of work required to equalize all $d+1$ histograms. In the special case $d=2$, it was observed [Erickson20]*Prop. 5 that there is a simple linear relationship between the EMD of three histograms, on one hand, and the three pairwise EMDs, on the other hand:

This identity instantly reminds one of Heron’s formula, where the histograms $h_{i}$ are vertices of a triangle, their EMD is the area, and the pairwise EMDs are the side lengths. In this EMD setting, however, the Heron analogue (3) is much simpler than the Euclidean version (1), since in (3) the area simply equals the semiperimeter. It is also shown in [Erickson20] that a simple formula of the kind in (3), expressing overall EMD exclusively in terms of the pairwise EMDs, cannot exist for $d>2$. The purpose of this paper, then, is to find the correct generalization of (3) in arbitrary dimensions.

As our primary tool, we introduce a combinatorial object $\Delta$ we call the earth mover’s (EM) simplex (see Definition 3.1). We endow $\Delta$ with a “volume” in such a way that, if the vertices of $\Delta$ are taken to be the cumulative histograms of $h_{0},\ldots,h_{d}$, then the volume of $\Delta$ equals ${\rm EMD}(h_{0},\ldots,h_{1})$. In this way, we translate the problem into that of expressing the volume of $\Delta$ in terms of its edge lengths. In fact, this “volume” is merely the first in a sequence of generalized volumes we define on $\Delta$; it turns out that the second generalized volume measures the failure of the obvious analogue of (3). Hence our main result (Theorem 4.1), a sort of Cayley–Menger formula for EM simplices, takes the especially nice form

We also prove a second volume formula for EM simplices (Theorem 4.3), this time in terms of the surface area ${\rm SA}(\Delta)$:

where $|{\rm Med}(\Delta)|$ is the number of elements contained in exactly half of the vertices (which, in an EM simplex, are themselves sets). We point out that in even dimensions, we automatically have $|{\rm Med}(\Delta)|=0$; we find it interesting that the dimensional parity affects the EMD in this way, since a similar effect has been observed with regard to its expected value [Erickson20]*§5.4.

In Section 5 we present a fully illustrated example of both main theorems, which may be helpful in understanding the definition of an EM simplex. We are also hopeful that the results in this paper might suggest a direction for future research by experts in topological data analysis, using the tools of persistent homology; see our closing remarks in Section 6.

Classically, the earth mover’s distance (EMD) measures the similarity between two histograms: the EMD is defined to be the minimum amount of work required to transform one histogram into the another. In this paper, the histograms we consider have bins $1,\ldots,n$, and some fixed number $m$ of data points. We define one unit of work to be the work required to move one data point by one bin. We denote a histogram by a lower-case $h=(h(1),\ldots,h(n))$, where $h(i)$ is the number of data points in bin $i$. We denote the cumulative histogram of $h$ by an upper-case $H=(H(1),\ldots,H(n))$, where $H(j)=\sum_{i=1}^{j}h(i)$. It will be convenient for us to identify $H$ with the set of dots in its dot diagram, as in the following example:

Note that in the language of combinatorics, each histogram can be identified with a unique (weak) composition of $m$ into $n$ parts, while a cumulative histogram is a partition of $\sum_{i}H(i)$ into $n$ parts. It is customary to identify a partition with its Ferrers diagram, which is essentially the dot diagram here (up to rotation by 180 degrees). By ignoring the last column of $H$, which always contains $m$ dots, it is easy to see [Erickson23]*§3 that the set of cumulative histograms is in bijection with the set of Ferrers diagrams fitting inside an $m\times(n-1)$ rectangle.

Given two histograms $h_{0},h_{1}$, it is well known that ${\rm EMD}(h_{0},h_{1})$ equals the $\ell_{1}$-norm of $H_{0}-H_{1}$, as a difference of functions on $\{1,\ldots,n\}$. (See  [Rabin]*eqn. (8) and Fig. 1; it follows that the EMD is a true metric on the space of histograms.) From the perspective of [Erickson23], this means that

where $H_{0}\,\scalebox{0.75}{$\triangle$}\,H_{1}\coloneqq(H_{0}\cup H_{1})\setminus(H_{0}\cap H_{1})=(H_{0}\setminus H_{1})\cup(H_{1}\setminus H_{0})$ denotes the symmetric difference. In words, the EMD is the number of dots occurring in exactly one of the two cumulative histograms; see the example in Figure 1.

The EMD has a natural generalization for any number of histograms, rather than only two at a time. (See, for example, [Bein] and [Kline] for computational treatments of the higher-dimensional earth mover’s problem in greater generality.) Given histograms $h_{0},\ldots,h_{d}$, one simply defines ${\rm EMD}(h_{0},\ldots,h_{d})$ to be the minimum amount of work required to transform all of the $h_{i}$ into a common histogram (allowing data points to be transported within each histogram).

In order to extend the conceptual method of Figure 1 beyond the classical case $d=1$, we require the correct generalization of the symmetric difference. It turns out that the key property of the symmetric difference (with regard to the EMD) was this: for each dot $x\in H_{1}\cup H_{2}$, the symmetric difference measures how far away $x$ is from either belonging to none of the $H_{i}$ or belonging to all of the $H_{i}$. When $d=1$ this is a binary measurement: if $x$ belongs to neither/both of the $H_{i}$, then it appears 0 times in the symmetric difference, and otherwise it appears 1 time in the symmetric difference. For arbitrary $d$, however, generalizing this measurement requires the symmetric difference to be a multiset: the multiplicity of each dot $x$ is either the number of $H_{i}$ containing $x$, or the number of $H_{i}$ not containing $x$, whichever is smaller.

Throughout the paper, we write $\uplus$ to denote the union of multisets, and we write $x^{m}$ to denote a multiset element with multiplicity $m$. If $\mathcal{X}$ is a family of sets, then for each $x\in\bigcup_{X\in\mathcal{X}}X$, its degree, written as $\deg_{\mathcal{X}}(x)$, is the number of sets $X\in\mathcal{X}$ such that $x\in X$.

See Figure 2 for a toy example, which we will revisit in Section 5.

Let $\Delta=\Delta(V)$ be the (abstract) $d$-simplex on the vertex set $V=\{v_{0},\ldots,v_{d}\}$. In other words, $\Delta$ is the power set of $V$, so that the elements (faces) of $\Delta$ are simply the subsets $F\subseteq V$. The dimension of a face is one less than its cardinality: hence we write $\dim F\coloneqq\#F-1$, and in particular we have $\dim\varnothing=-1$. By definition, $\dim\Delta\coloneqq\dim V=d$. The codimension of a face is $\operatorname{codim}F\coloneqq d-\dim F$. The 0-dimensional faces $\{v_{i}\}$ are called vertices, and the 1-dimensional faces $\{v_{i},v_{j}\}$ are called edges. The $(d-1)$-dimensional faces $\{v_{0},\ldots,\widehat{v}_{i},\ldots,v_{d}\}$ are called facets of $\Delta$, and the missing $v_{i}$ is called the vertex opposite the facet.

It is customary, when convenient, to view a face as the simplex it defines. For example, we call $F$ a facet of $G\in\Delta$ whenever $F\subset G$ with $\dim F=\dim G-1$, although technically it would be more proper to call $F$ a facet of $\Delta(G)$. In this case, we also say that $G$ is a cofacet of $F$. Clearly the number of facets of $G$ equals its cardinality $\#G$.

We denote the $k$-skeleton of $\Delta$ by ${\rm skel}_{k}(\Delta)\coloneqq\{F\in\Delta\mid\dim F\leq k\}$. Finally, the link of a face $F$ is the subsimplex of $\Delta$ containing all faces which are disjoint from $F$. (This is a special case of the standard definition of link in simplicial complexes.)

In our upcoming definition of an EM simplex, the role of vertices $v_{i}$ will be played by finite sets $X_{i}$. Hence let $\mathcal{X}=\{X_{0},\ldots,X_{d}\}$ be a family of finite sets, and from now on, let $\Delta=\Delta(\mathcal{X})$. We use the shorthand $\cup\mathcal{X}\coloneqq\bigcup_{X\in\mathcal{X}}X$, and we partition $\cup\mathcal{X}$ into three subsets according to degree:

(These are the elements contained in the minority, in the median number, or in the majority of the $X_{i}$, respectively.) Note that if $d$ is even, then ${\rm Med}(\mathcal{X})=\varnothing$. Define a map $\epsilon$ which assigns to each $x\in\cup\mathcal{X}$ a face $\epsilon(x)$ in the “half-skeleton” of $\Delta$, according to the memberships of $x$:

We now define a sequence $\lambda^{(0)},\lambda^{(1)},\lambda^{(2)},\ldots$ of face labelings, as follows. Begin by defining $\lambda^{(0)}\coloneqq\epsilon^{-1}$, thereby labeling each face $\mathcal{F}\in{\rm skel}_{\lfloor(d-1)/2\rfloor}(\Delta)$ by its fiber:

Then recursively define

Note that $\lambda^{(0)}(\mathcal{F})$ and $\lambda^{(1)}(\mathcal{F})$ are multiplicity-free (i.e., they are true sets), whereas for $i\geq 2$, the labels $\lambda^{(i)}(\mathcal{F})$ can be multisets. The reader may prefer to imagine constructing the labels $\lambda^{(i+1)}(\mathcal{F})$ as follows: starting with a clean slate, choose a face $\mathcal{G}$, and add one copy of its previous label $\lambda^{(i)}(\mathcal{G})$ to each facet $\mathcal{F}$ of $\mathcal{G}$. Doing this for all $\mathcal{G}$ where $\lambda^{(i)}(\mathcal{G})$ exists, the resulting multiset unions are precisely the new labels $\lambda^{(i+1)}(\mathcal{F})$. Hence, intuitively, one can regard each successive labeling as spreading $\#\mathcal{G}$ copies of the previous label of $\mathcal{G}$ across the boundary $\partial(\mathcal{G})$, for each face $\mathcal{G}$ in the appropriate skeleton.

Note that the domain of $\lambda^{(i)}$ is ${\rm skel}_{\lfloor(d-1)/2\rfloor-i}(\Delta)$, and so the nonempty labelings are given by the finite sequence $\lambda^{(0)},\ldots,\lambda^{(\lceil d/2\rceil)}$. From now on, we will use the familiar shorthand $\lambda\coloneqq\lambda^{(0)}$, $\lambda^{\prime}\coloneqq\lambda^{(1)}$, and $\lambda^{\prime\prime}\coloneqq\lambda^{(2)}$. These are the only labelings that play a role in this paper, and it will turn out that the notation is intentionally suggestive of derivatives.

We now make the two central definitions of this paper:

As mentioned in Section 3.1, each face $\mathcal{F}\in\Delta$ determines the EM simplex $\Delta(\mathcal{F})$, and so for notational clarity we will write ${\rm Vol}(\mathcal{F})\coloneqq{\rm Vol}(\Delta(\mathcal{F}))$.

The following proposition reveals the reason for choosing notation $\lambda,\lambda^{\prime},\lambda^{\prime\prime},\ldots$ suggestive of derivatives. Specifically, the generating function for $\#\epsilon(x)$ encodes all of the generalized volumes ${\rm Vol}_{i}(\Delta)$, as its $i$th derivatives evaluated at unity:

We conclude this section with the following corollary, which is the motivating fact behind the definition (and the name) of the EM simplex: