Earth Mover's Distance Foundations
Earth Mover's Distance (EMD) measures the least work needed to move one distribution into another. Here we mean Wasserstein-1 distance, written $W_1$: both distributions have total probability 1, and moving probability mass costs mass × distance. The ground distance tells us how far apart two outcomes are; for numbers on a line, it is $|x-y|$.
▶ Moving Mass to Match a Target
Orange mass must be moved to match the green target. Moving mass farther costs more. The arrows illustrate possible movements, not a complete transport plan.
Why It Is Different
KL and JS compare probability assigned to matching bins. EMD asks how far mass must travel. If two image distributions shift by a few pixels, EMD can recognize that the distributions are close geometrically, while bin-wise divergences may treat them as very different.
What Exactly Are We Minimizing?
Let $P$ place probability $a_i$ at each source location $x_i$, and let $Q$ need probability $b_j$ at each target location $y_j$. A transport plan $T_{ij}$ says how much probability to move from $x_i$ to $y_j$. Its cost is the sum of mass times ground distance, $d(x_i,y_j)$:
$$W_1(P,Q)=\min_T\sum_{i,j}T_{ij}\,d(x_i,y_j).$$The plan must move exactly the available mass out of each source and deliver exactly the required mass to each target:
$$T_{ij}\geq0,\qquad\sum_jT_{ij}=a_i,\qquad\sum_iT_{ij}=b_j.$$For example, if all of $P$ sits at 0 and all of $Q$ sits at 3, the only choice is to move the whole unit of probability three units. Thus $W_1(P,Q)=1\times3=3$. The distributions do not overlap, but their transport distance is finite.
EMD Properties for Interviews
These properties assume the ground distance is a metric: nonnegative, zero only between identical locations, symmetric, and obeying the triangle inequality. Ordinary Euclidean distance qualifies.
| Question | Answer |
|---|---|
| Negative? | No: $W_1\geq0$. Every moved amount and every distance is nonnegative, so even the cheapest plan cannot have negative cost. |
| When zero? | Exactly when $P=Q$. Matching distributions can leave all mass where it is; differing distributions require some movement. |
| Symmetric? | Yes: $W_1(P,Q)=W_1(Q,P)$. Reverse every movement in a plan: it moves the target back to the source for the same cost. |
| A metric? | Yes. It also satisfies the triangle inequality: going directly from $P$ to $R$ costs no more than going via $Q$. See the equation below. |
| Needs overlap? | No. Unlike KL, disjoint supports do not force infinity. Moving all probability from 0 to 3 simply costs 3. |
| Upper limit? | No universal limit such as 1. If all ground distances in the problem are at most $D$, however, then $W_1\leq D$: total mass is 1. |
| What units? | The same units as the ground distance. With Euclidean distance, doubling every coordinate doubles $W_1$; translating both distributions equally leaves it unchanged. |
| Always finite? | For finite histograms with finite ground distances, yes. On an unbounded space, finite average distance from a fixed origin for both distributions guarantees finiteness; without that condition, it can be infinite. |
| Equal mass? | Balanced EMD requires equal total mass, usually 1. It does not require equal sample counts. Normalize counts to compare distributions; use an unbalanced transport formulation if differences in total mass should matter. |
The triangle inequality is:
$$W_1(P,R)\leq W_1(P,Q)+W_1(Q,R).$$Transport through an intermediate distribution gives a possible route. Because the underlying ground distance obeys the triangle inequality, sending each piece directly cannot cost more. The cheapest direct plan can only improve on that route. The metric construction is covered in Peyré's optimal-transport notes.
For a numerical cost matrix, a complete transport plan, and examples in model monitoring and GANs, continue to Optimal Transport in Machine Learning.