Trasportation metric (AKA Earth-Mover's, Wasserstein, etc.) as "natural" / "induced"?

Question

Context: Given a discrete finite metric space $X$ (in my case X={0,1}$^n$ with the Hamming/L$_1$ distance), I need to define the natural or canonical metric on the set of all probability distributions over $X$ (call it $D(X)$) which extends the given metric.

I have read in several places [*] that the Earth-Mover's is the natural, or induced, or most canonical extension.

I would like to know whether it is proved (or can be easily proven) that it is the only, or indeed the canonical metric that can be given to the set of distributions over $X$ so that when restricted to

D1(X) = {d in D(X) | d(x)=0 for all x in X, except one}

(the distributions whose support is just one element), you obtain the metric of $X$.

[*] mathoverflow: Distance metric between two sample distributions [...], or google "EMD naturally extends the notion of distance" and you'll find several papers saying a similar thing, as a "fact", without proof or reference.

Answer 1

Okay, so $X$ is a finite metric space and $D(X)$ is the positive part of the unit sphere of $l^1(X)$. We can consider $X$ as sitting inside $D(X)$ by identifying a point $x \in X$ with the function that is $1$ at $x$ and $0$ elsewhere.

The literal question you have asked is whether the mass transport metric on $D(X)$ is the only metric on $D(X)$ whose restriction to $X$ recovers the original metric on $X$. The answer to this question is clearly no; if you want to add a point to a metric space you generally have a lot of freedom to assign distances from it to the other points. All the more so if you are adding many new points.

But you probably meant to take the affine structure of $D(X)$ into account. $D(X)$ is the convex hull of $X$, so we can ask: if $X$ is isometrically embedded in a Banach space $E$, is the norm on its convex hull in $E$ uniquely determined? The answer is still no. For example, let $X$ have three elements, such that the distance between any two of them is $1$. We can embed $X$ as the vertices of an equilateral triangle in the euclidean plane, or we can embed it as the points $(0,1)$, $(1,1)$, and $(1,0)$ in $l^\infty_2$. The two metrics on the convex hull of $X$ aren't the same. (Look at the distance from the average of two of the points to the third.)

However, you also asked whether the mass transport metric is "canonical". Yes, it is. It is universal in the following sense:

Theorem. Let $X$ be a metric space and let $e \in X$. Then there is a Banach space $AE(X)$ together with an isometric embedding $\iota: X \to AE(X)$ such that $\iota(e) = 0$, and such that if $f: X \to E$ is any nonexpansive map from $X$ into any Banach space $E$ with $f(e) = 0$, then there is a unique nonexpansive linear map $T: AE(X) \to E$ such that $T \circ \iota = f$.

The mass transport metric is the restriction of the metric on $AE(X)$ to the convex hull of $X$. So this theorem could be rephrased in terms of the mass transport metric being the universal metric on $D(X)$ relative to nonexpansive affine maps. In other words, it is the metric for which distances are as large as possible, given the original metric on $X$. There's a nice little book on Lipschitz algebras that covers this material, but I forget the author.