1
$\begingroup$

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$?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Gilles Mordant Oct 23 '20 at 13:19
  • $\begingroup$ 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}}.$$ $\endgroup$ – Francesco Nobili Oct 23 '20 at 13:49
  • $\begingroup$ I refined my question since there are too many "lax" upper-bounds available... $\endgroup$ – BLBA Oct 23 '20 at 17:09
3
$\begingroup$

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<x_{n:j+1}),$$ where $x_{n:1}<\cdots<x_{n:n}$ 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}<u\le s_j)$$ 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.

$\endgroup$
14
  • $\begingroup$ Why did you only state an inequality? Isn't that the exact value of the Wasserstein distance (you missed an exponent p btw)? $\endgroup$ – alesia Oct 23 '20 at 18:33
  • $\begingroup$ @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 $\endgroup$ – Iosif Pinelis Oct 23 '20 at 18:53
  • $\begingroup$ The first equation p 10 in math.cmu.edu/~mthorpe/OTNotes says it's true for all p $\endgroup$ – alesia Oct 23 '20 at 19:19
  • 1
    $\begingroup$ 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). $\endgroup$ – Dirk Nov 5 '20 at 11:56
  • 1
    $\begingroup$ (The result is in "On a Formula for the L2 Wasserstein Metric between Measures on Euclidean and Hilbert Spaces" by Gelbrich) $\endgroup$ – Dirk Nov 5 '20 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.