# Relationship between a certain binary optimal transport and total-variation of modified distributions

Let $$\mathcal X$$ be a Polish space, and let $$(N_x)_{x \in \mathcal X}$$ be a system of closed neighborhoods in $$\mathcal X$$. Define $$\Omega := \{(x,x') \in \mathcal X^2 \mid N_x \cap N_{x'} = \emptyset\}$$, assumed to be open in $$\mathcal X^2$$. For example in a Banach space $$\mathcal X$$, an example would be $$N_x = x + \varepsilon\mathbb B$$ with $$\varepsilon > 0$$, and this would lead to $$\Omega := \{(x,x') \in \mathcal X^2 \mid \|x-x'\| > 2\varepsilon\}$$.

Now, let $$\mu$$ and $$\nu$$ be probability measures, and consider the quantity $$c_\Omega(\mu,\nu)$$ defined by

$$c_\Omega(\mu,\nu) := \inf_{\gamma \in \Pi(\mu,\nu)}\gamma(\Omega).$$ This is nothing but the transportation distance between $$\mu$$ and $$\nu$$, for the binary ground cost given by $$c_\Omega(x,x') = 1$$ if $$(x,x') \in \Omega$$; $$c_\Omega(x,x') = 0$$ else.

Finally, define $$d_N(\mu,\nu) := \inf_{a_1, a_2} \text{TV}({a_1}_{\#}\mu,{a_2}_{\#}\nu),$$ where the infimum is take over all measurable $$a_1, a_2:\mathcal X \rightarrow \mathcal X$$ such that $$a_1(x), a_2(x) \in N_x$$ for all $$x \in \mathcal X$$, and $$a_{\#}\mu$$ denotes the pushforward of $$\mu$$ under $$a$$

# Question

• Is there any relationship (equality, inequality, etc.) between $$c_\Omega(\mu,\nu)$$ and $$d_N(\mu,\nu)$$ ?

# Observations

By data-processing inequality, $$\text{TV}(a_{\#}\mu,a_{\#}\nu) \le \text{TV}(\mu,\nu)$$ and so $$d_N(\mu,\nu) \le \text{TV}(\mu,\nu)$$.

Claim. Let us define a relaxation of $$d_N$$ as $$\tilde d_N(\mu,\nu)=\inf_{\gamma_a,\gamma_b} TV(\pi^2_\#\gamma_a,\pi^1_\#\gamma_b)$$ subject to $$\pi^1_\# \gamma_a = \mu$$ and $$\pi^2_\# \gamma_b =\nu$$ and $$\gamma_a,\gamma_b$$ are concentrated on $$D_\epsilon = \{(x,x')\in \mathcal{X}^2; \Vert x-x'\Vert\leq \epsilon\}$$ (here $$\pi^i$$ is the projection on the $$i$$-th factor of $$\mathcal{X}^2$$). Then it holds $$2 c_{\Omega}(\mu,\nu) = \tilde d_N(\mu,\nu) \leq d_N(\mu,\nu) \tag{1},$$

where the inequality is an equality if $$\mu$$ and $$\nu$$ are absolutely continuous, but might be strict otherwise (e.g. on the real line, $$\mu=\frac13 \delta_{-2\epsilon}+\frac13 \delta_{0}+\frac13 \delta_{2\epsilon}$$ and $$\nu=\frac12 \delta_{-\epsilon}+\frac12 \delta_\epsilon$$ has $$d_N(\mu,\nu)=2/6$$ and $$\tilde d_N(\mu,\nu)=0$$).

Proof. The constructions are a bit tedious to describe, so I will not go through every detail. We consider the intermediate quantity $$E(\mu,\nu):=\inf_{\gamma\in \Pi_{\leq}(\mu,\nu)\\ \mathrm{spt}(\gamma)\subset D_{2\epsilon}} 1 - \gamma(\mathcal{X}^2) \tag{2}$$ where $$\Pi_{\leq}$$ denotes the set of partial transport plans, i.e. probabilities on $$\mathcal{X}^2$$ with marginals smaller than $$\mu$$ and $$\nu$$ respectively.

First, let us show that $$c_\Omega=E$$. Let $$\gamma \in \Pi(\mu,\nu)$$ and let $$\tilde \gamma$$ be its restriction to $$D_{2\epsilon}$$. Then $$\tilde \gamma$$ is feasible for $$E$$ and it holds $$\gamma(\Omega)=1-\tilde\gamma(\mathcal{X^2})$$ so $$E\leq c_\Omega$$. Conversely, let $$\gamma$$ be feasible for $$E$$ and consider any $$\tilde \gamma\in \Pi(\mu-\pi^1_\#\gamma, \nu-\pi^2_\#\gamma)$$. Then $$\gamma +\tilde \gamma$$ is feasible for $$c_\Omega$$ and $$(\gamma+\tilde \gamma)(\Omega)= \tilde \gamma(\Omega)\leq \tilde \gamma(\mathcal{X^2}) = 1-\gamma(\mathcal{X}^2)$$ so $$c_\Omega\leq E$$ and thus $$c_\Omega=E$$.

Let us show now that $$E=\tilde d_N$$. Consider the maps $$T_a,T_b,D$$ defined by $$T_a(x,y)=(x,(x+y)/2),\quad T_b(x,y)=((x+y)/2,y),\quad D(x)=(x,x).$$ Let $$\gamma$$ be feasible for $$E$$ and consider $$\gamma_a = (T_a)_\# \gamma + D_\# (\mu-\pi^1_\#\gamma)$$ and $$\gamma_b = (T_b)_\# \gamma + D_\# (\nu-\pi^2_\#\gamma)$$. Then $$(\gamma_a,\gamma_b)$$ is feasible for $$\tilde d$$ and $$TV(\pi^2_\#\gamma_a,\pi^1_\#\gamma_b)\leq (\mu-\pi^1_\#\gamma)(\mathcal{X})+ (\nu-\pi^2_\#\gamma)(\mathcal{X}) = 2(1-\gamma(\mathcal{X}^2))$$ because the second marginal of $$(T_a)_\# \gamma$$ and the first marginal of $$(T_b)_\# \gamma$$ agree by construction. Thus $$d_N\leq 2E$$. Conversely, let $$\gamma_a,\gamma_b$$ be feasible for $$\tilde d_N$$, and let $$\tilde \gamma_a\leq \gamma_a$$ and $$\tilde \gamma_b\leq \gamma_b$$ be such that $$\pi^2_\#\tilde \gamma_a = \pi^1_\#\gamma_b = (\pi^2_\# \gamma_a)\wedge (\pi^1_\# \gamma_b)$$ where $$\wedge$$ is the "pointwise" minimum of two measures (they can be built with the disintegration theorem). Now build $$\tilde \gamma$$ feasible for $$E$$ by gluing together $$\tilde \gamma_a$$ and $$\tilde \gamma_b$$, see [1, Lem. 5.5]. It holds $$TV(\pi^2_\#\gamma_a ,\pi^1_\# \gamma_b ) = 2(1-\pi^2_\#\gamma_a \wedge \pi^1_\# \gamma_b)(\mathcal{X}) = 2(1-\tilde \gamma(\mathcal{X}^2)) \tag{3}.$$ Thus $$2E\leq \tilde d_N$$ hence $$2E=\tilde d_N$$.

The fact that $$\tilde d_N\leq d_N$$ in general is due to the fact to any transport map $$a$$ satisfying $$\Vert a(x) -x\Vert\leq \epsilon$$ corresponds a deterministic transport plan $$(\mathrm{id}, a)_\# \mu$$ supported on $$D_\epsilon$$. Finally, the fact that $$\tilde d_N=d_N$$ when $$\mu$$ and $$\nu$$ are absolutely continuous is a consequence of the existence of an optimal transport map for the $$W_\infty$$ distance, see [1, Thm. 3.24]. Indeed, if $$(\gamma_a,\gamma_b)$$ is feasible for $$\tilde d_N$$, then $$W_\infty(\mu,\pi^2_\#\gamma_a)\leq \epsilon$$ and there exists a measurable map $$a_1:\mathcal{X}\to\mathcal{X}$$ such that $$\Vert a_1(x)-x\Vert\leq \epsilon$$ $$\mu$$-a.e. and $$(a_1)_\# \mu = \pi^2_\#\gamma_a$$ (one can build $$a_2$$ similarly).

[1] Santambrogio, Filippo, Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling

• Wow! Thanks very much for such a indepth answer. – dohmatob Sep 27 '19 at 12:57
• BTW, we both agree that your arguments carry over to the case where $\Omega$ is constructed from a general system $N_x$, and no just balls. Right ? – dohmatob Sep 27 '19 at 12:58
• You're welcome! I have worked with similar manipulations in relation to optimal partial transport. The argument extends to the general systems of closed neighborhoods, except that I am not sure that the existence of transport maps (last argument) has been proved in that setting. – Lénaïc Chizat Sep 29 '19 at 18:40
• OK, thanks. Could you recommend any good refs on the subject of "optimal partial transport" ? – dohmatob Sep 29 '19 at 21:28
• A good reference is Figalli's paper. By the way, in my answer I used the definition of TV-norm that coincides with L1 norm for densities (which is twice the TV-norm sometimes used by probabilists). – Lénaïc Chizat Sep 30 '19 at 7:25