# Closed-form upper-bounds for Wasserstein distance between finite measures

Let $$x_1,\dots,x_n,y_1,\dots,y_n\in \mathbb{R}$$ and such that $$x_i\neq x_j$$ and $$y_i\neq y_j$$ if $$i\neq j$$. Let $$a,b$$ be elements of the probability n-simplex. Define the measures $$\mu\triangleq \sum_{i=1}^n a_i \delta_{x_i}$$ and $$\nu\triangleq \sum_{i=1}^n b_i \delta_{y_i}$$. Are there known, (not too lax) upper-bounds for $$W_p(\mu,\nu) \leq M\left(x_1,\dots,x_n,y_1,\dots,y_n,a,b\right)$$ for some continuous function $$M$$; known in closed-form such that $$M(x_1,\dots,x_n,x_1,\dots,x_n,a,b)=0.$$

Where $$W_p$$ is the Wasserstein-1 distance, for some $$1\leq p<\infty$$?

• The Wasserstein distance is an infimum, so should be bounded by any feasible matching. Any feasible assignment based on a greedy approach will make do. Control by weighted total variation (see the book by Villani, 2008) could also help. – Gilles Mordant Oct 23 '20 at 13:19
• The worst you can do, is the 'democratic' coupling $\pi := \sum_{i,j} a_ib_i\delta_{x_i}\otimes \delta_{y_j}$, which gives you the upper bound $$M= ( \sum_{i,j} a_ib_j |x_i-y_j|^p )^{\frac{1}{p}}.$$ – Francesco Nobili Oct 23 '20 at 13:49
• I refined my question since there are too many "lax" upper-bounds available... – BLBA Oct 23 '20 at 17:09

Let $$F(x):=\mu((-\infty,x])=\sum_i a_i\,1(x_i\le x) =\sum_{j=1}^n s_j\,1(x_{n:j}\le x where $$x_{n:1}<\cdots are the values $$x_1,\dots,x_n$$ put in the increasing order (with $$x_{n:n+1}:=\infty$$), $$s_j:=\sum_{i=1}^j a_{n:i},$$ and $$a_{n:1},\dots,a_{n:n}$$ are the values $$a_1,\dots,a_n$$ put in the increasing order of the $$x_k$$'s, so that, if $$x_{n:i}=x_k$$ for some $$k$$, then $$a_{n:i}=a_k$$. So, $$F$$ is the cdf of the probability measure $$\mu$$. Similarly considered is the function $$G$$ defined as the cdf of the probability measure $$\nu$$.

Consider then the generalized inverse/quantile function $$F^{-1}\colon(0,1)\to\mathbb R$$ defined by $$F^{-1}(u):=\inf\{x\in\mathbb R\colon F(x)\ge u) \\ =\max\{x\in\mathbb R\colon F(x)\ge u) \\ =\sum_{j=1}^n x_{n:j}\,1(s_{j-1} for $$u\in(0,1)$$, with the similarly defined and considered $$G^{-1}$$. Let $$U$$ be a random variable (r.v.) uniformly distributed on $$(0,1)$$. Then the distributions of the r.v.'s $$X:=F^{-1}(U)$$ and $$Y:=G^{-1}(U)$$ will be $$\mu$$ and $$\nu$$, respectively. Finally, let $$M(x_1,\dots,x_n,y_1,\dots,y_n,a,b):=M(\mu,\nu) \\ :=(E|X-Y|^p)^{1/p} =\Big(\int_0^1|F^{-1}(u)-G^{-1}(u)|^p\,du\Big)^{1/p}.$$ Then $$W_p(\mu,\nu)\le M(x_1,\dots,x_n,y_1,\dots,y_n,a,b)$$ and
$$M(x_1,\dots,x_n,x_1,\dots,x_n,a,a)=0,$$ as desired.

Remark: The upper bound $$M(\mu,\nu)$$ given above is actually the exact value of the Wasserstein distance for $$p\ge1$$, according to the last sentence of Theorem 2.1 -- thank you alesia for this reference.

• Why did you only state an inequality? Isn't that the exact value of the Wasserstein distance (you missed an exponent p btw)? – alesia Oct 23 '20 at 18:33
• @alesia : The upper bound $M(\mu,\nu)$ given in the answer will in general be the exact value of the Wasserstein distance only for $p=1$ -- see e.g. arxiv.org/pdf/1912.04945.pdf – Iosif Pinelis Oct 23 '20 at 18:53
• The first equation p 10 in math.cmu.edu/~mthorpe/OTNotes says it's true for all p – alesia Oct 23 '20 at 19:19
• For higher dimensions one could use that $W_p(\mu,\nu)\geq \sup\{\int f\,d(\mu-\nu)\mid Lip(f)\leq 1\}$ so any Lipschitz-1 function gives a lower bound. One may construct some $f$ in some greedy fashion (this does not lead to an "explicit" formula, but a straightforward algorithm for a lower bound). – Dirk Nov 5 '20 at 11:56
• (The result is in "On a Formula for the L2 Wasserstein Metric between Measures on Euclidean and Hilbert Spaces" by Gelbrich) – Dirk Nov 5 '20 at 11:57