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$ Oct 23, 2020 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$ Oct 23, 2020 at 13:49
  • $\begingroup$ I refined my question since there are too many "lax" upper-bounds available... $\endgroup$
    – AIM_BLB
    Oct 23, 2020 at 17:09

1 Answer 1

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, 2020 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$ Oct 23, 2020 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, 2020 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, 2020 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, 2020 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.