The Earth mover's distance (EMD) is a measure of dissimilarity between two probability distributions over a metric space. It originates from the theory of optimal transport and quantifies the minimum “cost” required to transform one distribution into the other, where the cost is defined as the amount of “earth” (probability mass) moved multiplied by the distance it is moved.
Mathematical definition
Given two discrete distributions $P = {(p_i, x_i)}{i=1}^m$ and $Q = {(q_j, y_j)}{j=1}^n$, where $p_i$ and $q_j$ are non‑negative weights that sum to one, and $d(x_i, y_j)$ is a ground distance between locations $x_i$ and $y_j$, the Earth mover's distance is the solution of the linear programming problem:
$$ \text{EMD}(P,Q) = \min_{f_{ij}} \sum_{i=1}^m \sum_{j=1}^n f_{ij}, d(x_i, y_j) $$
subject to
$$ \begin{aligned} f_{ij} &\ge 0 \quad \forall i,j,\ \sum_{j=1}^n f_{ij} &\le p_i \quad \forall i,\ \sum_{i=1}^m f_{ij} &\le q_j \quad \forall j,\ \sum_{i=1}^m \sum_{j=1}^n f_{ij} &= \min\Bigl(\sum_{i=1}^m p_i,\ \sum_{j=1}^n q_j\Bigr). \end{aligned} $$
Here $f_{ij}$ denotes the flow of mass from $x_i$ to $y_j$. The optimal value represents the least total work required to “move” one distribution onto the other. When the total masses are equal (both sum to 1), the denominator is often omitted, and the EMD coincides with the first Wasserstein distance (also called the 1‑Wasserstein metric).
Historical background
The concept derives from the Monge–Kantorovich optimal transport problem, first formulated by Gaspard Monge in 1781 and later generalized by Leonid Kantorovich in the 1940s. The specific term “Earth mover’s distance” was popularized in the computer vision community in the late 1990s and early 2000s, notably in the work of Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas (1998) for comparing color histograms.
Applications
- Computer vision and image retrieval: Comparing color, texture, or shape histograms where spatial relationships matter.
- Machine learning: As a loss function for generative models (e.g., Wasserstein GANs) and for domain adaptation.
- Signal processing: Measuring differences between spectral distributions.
- Document analysis: Comparing term frequency vectors in natural‑language processing.
- Geosciences and remote sensing: Evaluating similarity of spatial patterns (e.g., land‑cover maps).
Computational considerations
Exact computation of the EMD requires solving a linear program, which can be computationally expensive for large distributions. Various algorithms and approximations have been developed, including the network simplex method, the Hungarian algorithm for special cases, and entropy‑regularized Sinkhorn iterations that provide faster, differentiable approximations.
Related concepts
- Wasserstein distance: A family of metrics parameterized by an order $p$; the Earth mover’s distance corresponds to the case $p = 1$.
- Rubner–Tomasi–Guibas algorithm: An early efficient implementation for histogram comparison.
- Sinkhorn distance: An entropy‑regularized version of the optimal transport problem that approximates the EMD while enabling gradient‑based optimization.
References
- Rubner, Y., Tomasi, C., & Guibas, L. J. (1998). A Metric for Distribution‑Based Image Retrieval. IEEE International Conference on Computer Vision (ICCV).
- Villani, C. (2008). Optimal Transport: Old and New. Springer.
- Arjovsky, M., Chintala, S., & Bottou, L. (2017). Wasserstein GAN. International Conference on Machine Learning (ICML).
The Earth mover’s distance is an established concept in mathematics and computer science, widely cited in scholarly literature and employed across multiple technical domains.
