One-Dimensional Wasserstein Distance

July 2026 · 15 min read

In one dimension, Earth Mover's Distance has a simple cumulative formula. If $F$ and $G$ are cumulative distribution functions, then

The area between the CDFs is exactly the amount of mass that must cross each location. This makes 1D EMD easy to compute from sorted samples or histogram bins.

Histogram Computation

For equal-width bins, scan from left to right. Track the cumulative surplus between source and target. Add the absolute surplus at each step. This works because surplus mass must be carried into future bins.

double emd_1d(const vector<double>& p, const vector<double>& q, double width) {
    double carry = 0.0, cost = 0.0;
    for (size_t i = 0; i < p.size(); ++i) {
        carry += p[i] - q[i];
        cost += fabs(carry) * width;
    }
    return cost;
}

Interpretation

If the source has too much mass on the left and the target has too much on the right, the carry stays positive for several bins. The longer it stays positive, the farther mass must move, and the larger the cost.