3
$\begingroup$

In "SNOWFLAKE UNIVERSALITY OF WASSERSTEIN SPACES" by ALEXANDR ANDONI, ASSAF NAOR, AND OFER NEIMAN they have the following notation:

  • For a metric space X they write $\mathcal{P}_1(X)$ to denote $1$-Wasserstein space over $X$ aka Earthmover space aka Kantorovich-Rubinstein space etc.
  • $\mathcal{Z} = (Lip([0,1]^2))^*$ is a dual of real-valued Lipschitz functions on the square $[0,1]^2$. (I assume that we always take the Lipschitz constant as the norm on Lipschitz functions.)

And they mention the following thing that I fail to understand:

As explained in [71], every finite subset of $\mathcal{Z}$ embeds into $\mathcal{P}_1(\mathbb{R}^2)$ with distortion arbitrarily close to 1,...

[71] A. Naor and G. Schechtman. Planar earthmover is not in L1. SIAM J. Comput., 37(3):804–826 (electronic), 2007.

From [71] I learned that by applying Kantorovich duality we can get that if $X$ is finite then every finite subset of $(Lip_0(X))^*$ embeds into $\mathcal{P}_1(X)$ with distortion arbitrarily close to 1. (Here $Lip_0(X)$ is the space of Lipschitz functions which are $0$ at some fixed point $x_0$.)

It feels like the argument should be that for a given finite subset of $\mathcal{Z}$ and a fixed D > 1 we are able to embed it with distortion < D into $(Lip_0(\mathcal{N}))^*$, where $\mathcal{N}$ is a small net in $[0,1]^2$. But I can't figure it out or locate an argument in [71].

$\endgroup$
0
$\begingroup$

What the reference is saying is: for every finite metric space $X$, and every $D>0$, there is an embedding $f\colon (\left(\mathrm{Lip}_0(X)\right)^*\to \mathcal{P}_1(X)$ of distortion at most $D$.

Now suppose $X\subset \cal{Z}$ and observe that this induces an isometric embedding $\mathcal{P}_1(X) \to \mathcal{P}_1(\mathcal{Z})$ (every measure on $X$ is a convex combination of delta-measures, which make sense as measures on $\mathcal{Z}$ as well). In particular the low-distortion map $f$ above is also a low-distortion map into $\mathcal{P}_1(\mathcal{Z})$.

$\endgroup$
4
  • $\begingroup$ $\mathcal{P}_1(\mathcal{Z})$ is a monster space $\endgroup$ – Vladimir Zolotov Feb 16 at 23:15
  • $\begingroup$ The target space is much more modest in the claim. $\endgroup$ – Vladimir Zolotov Feb 16 at 23:21
  • $\begingroup$ Hey Lior, thanks for thinking about the thing and replying. $\endgroup$ – Vladimir Zolotov Feb 16 at 23:29
  • $\begingroup$ Sorry -- my answer is totally wrong. I'll try fixing it. $\endgroup$ – Lior Silberman Feb 17 at 0:21

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.