# Calculating Wasserstein's distance between an empirical distribution and a combination of normal distributions

## Context of the problem

Let $\xi$ be a random variable (with real value) with support $\Xi=\mathbb{R}$ and $\xi_{1},\ldots,\xi_{N}$ be a sample of $\xi$. We consider the empirical probability $$\widehat{\mathbb{P}}_{N}:=\frac{1}{N}\sum_{i=1}^{N}\delta_{\xi_{i}}.$$

For each $\alpha\geq 0$ we consider the density function $$g_{\alpha}(\xi):=\frac{1}{N\alpha}\sum_{i=1}^{N}\mathcal{K}\left(\frac{\xi_{i}-\xi}{\alpha}\right)$$ where $\mathcal{K}$ is any density function, for example a Standard Normal. Note that $g_{\alpha}$ determines the probability

$$\mathbb{Q}_{\alpha}(A)=\int_{A}g_{\alpha}(\xi)m(d\xi)$$ where $m$ is the Lebesgue measure in $\mathbb{R}$ and $A$ is any measurable set. From this we can infer that for any measurable function $\Psi$ $$\int_{\mathbb{R}}\Psi(\xi)\mathbb{Q}(d\xi)=\int_{\mathbb{R}}\Psi(\xi)g_{\alpha}(\xi)m(d\xi).$$ [I am not sure if the latter is correct in general, clearly for simple functions if it is valid.]

Definition (Wasserstein distance) The Wasserstein distance $W_{p}(\mu,\nu)$ between $\mu,\nu\in\mathcal{P}_{p}(\Xi)$ is defined by $$W_{p}^{p}(\mu,\nu):=\min_{\lambda\in\mathcal{P}(\Xi\times\Xi)}\left\{\int_{\Xi\times\Xi}d^{p}(\xi,\zeta)\lambda(d\xi,d\zeta)\: :\: \lambda(\cdot \times\Xi)=\mu(\cdot),\: \lambda(\Xi\times\cdot)=\nu(\cdot)\right\}$$ where $$\mathcal{P}_{p}(\Xi):=\left\{\mu\in\mathcal{P}(\Xi)\: :\: \int_{\Xi}d^{p}(\xi,\zeta_{0})\mu(d\xi) < \infty\ \mbox{for some }\zeta_{0}\in\Xi\right\}$$ and $d$ is a metric in $\Xi$.

Proposition: (Dual representation of Wasserstein distance) $$W_{p}^{p}(\mu,\nu)=\sup_{u\in L^{1}(\mu),v\in L^{1}(\nu)}\left\{\int_{\Xi}u(\xi)\mu(d\xi)+\int_{\Xi}v(\zeta)\nu(d\zeta)\: : \: u(\xi)+v(\zeta)\leq d^{p}(\xi,\zeta),\: \forall \xi,\zeta\in\Xi\right\}$$

## The problem

I need to explicitly calculate the expression $$\sup_{\alpha\geq 0}\left\{\int_{\Xi}\Psi(\xi)\mathbb{Q}_{\alpha}(d\xi)-\lambda W_{p}^{p}\left(\widehat{\mathbb{P}}_{N},\mathbb{Q}_{\alpha}\right) \right\}\tag{\bigstar}$$ for $\lambda\geq 0$, $\mathcal{K}$ as the standard normal density and $\Psi$ defined by $$\Psi(\xi):=\left\{\begin{array}{ll}1 & \mbox{If }\xi\in[x,x+h] \\ 0 & \mbox{If } \xi\notin[x,x+h] \end{array}\right. \tag{\clubsuit}$$ where $x\in\mathbb{R}$ and $h>0$ are fixed.

Remark: I have treated this problem for a considerable time, this has led me to lower my ambition and now my intention is to be able to find at least a reformulation of $(\bigstar)$ where the measures $\widehat{\mathbb{P}}_{N}$ and $\mathbb{Q}_{\alpha}$ disappear from the problem. Also, note that in this problem it is crucial to be able to calculate $W_{p}^{p}\left(\widehat{\mathbb{P}}_{N},\mathbb{Q}_{\alpha}\right)$, that is, the Wasserstein's distance between an empirical distribution and a combination of normal distributions.

The comments of Iosif Pinelis and Dirk motivated me to write this addendum. The reason why I wrote this post is to be able to approach the moment problem
$$\inf_{y\in Y}\mathbb{E}_{\mathbb{P}}[\Psi(y,\xi)] \tag{\blacklozenge}$$ a form is approaching it superiorly in the following way: $$\inf_{y\in Y}\sup_{\mathbb{Q}\in\mathcal{B}_{\varepsilon}^{p}(\widehat{\mathbb{P}}_{N})}\mathbb{E}_{\mathbb{Q}}[\Psi(y,\xi)] \tag{I}$$

where $\mathcal{B}_{\varepsilon}^{p}(\widehat{\mathbb{P}}_{N})$ is of open ball of radius $\varepsilon$ and center $\widehat{\mathbb{P}}_{N}$ respect to Wasserstein metric $W_{p}$. Therefore, omitting the presence of $y$ the importance falls on the problem $$v_{p}:=\sup_{\mathbb{Q}\in\mathcal{B}_{\varepsilon}^{p}(\widehat{\mathbb{P}}_{N})}\mathbb{E}_{\mathbb{Q}}[\Psi(\xi)].$$

Recent articles (see this link in Theorem 1) show that under certain conditions about $\Psi$ the problem $v_{p}$ satisfies strong duality where the dual problem is $$\begin{array}{rcl}v_{d}&:=&{\displaystyle\inf_{\lambda\geq 0}\left\{\lambda \varepsilon^{p} -\int_{\Xi}\inf_{\xi\in\Xi}\left[\lambda d^{p}(\xi,\zeta)-\Psi(\xi)\right]\widehat{\mathbb{P}}_{N}(d\zeta) \right\}}\\ &=& {\displaystyle\inf_{\lambda\geq 0}\left\{\lambda \varepsilon^{p} +\frac{1}{N}\sum_{i=1}^{N}\sup_{\xi\in\Xi}\left[\Psi(\xi)-\lambda d^{p}(\xi,\xi_{i})\right] \right\}} \end{array} \tag{\blacktriangle}$$

From the latter it is easy to infer that $$\sup_{\mu\in\mathcal{P}(\Xi)}\left\{\int_{\Xi}\Psi(\xi)\mu(d\xi)-\lambda W_{p}^{p}\left(\widehat{\mathbb{P}}_{N},\mu\right) \right\}=\frac{1}{N}\sum_{i=1}^{N}\sup_{\xi\in\Xi}\left[\Psi(\xi)-\lambda d^{p}(\xi,\xi_{i})\right].$$

For me this is a very comfortable formulation, I want to find a similar formulation for ($\bigstar$), that's what I mean when I say "explicitly computable", this formulation is very comfortable since depending on the form of $\Psi$ and $\Xi$ (for example, $\Psi$ in the form ($\clubsuit$) and $\Xi=\mathbb{R}$) the problem ($\blacktriangle$) it can become a finite convex optimization problem.

But I want to go further, note that in this problem its optimal value can be reached by a discrete distribution, for my purposes (which I will gladly disclose if you ask me) that is a problem, in that sense I decided to intersect the ball $\mathcal{B}_{\varepsilon}^{p}(\widehat{\mathbb{P}}_{N})$ with the distributions of the form $\mathbb{Q}_{\alpha}$, note that the distributions $\mathbb{Q}_{\alpha}$ are continuous, my intention is to approximate ($\blacklozenge$) by means of the formulation $$\inf_{y\in Y}\sup_{\mathbb{Q}\in\mathcal{B}_{\varepsilon}^{p}(\widehat{\mathbb{P}}_{N})\cap \mathcal{Q}}\mathbb{E}_{\mathbb{Q}}[\Psi(y,\xi)] \tag{II}$$ where $\mathcal{Q}:=\left\{\mathbb{Q}_{\alpha}\: :\: \alpha\geq 0\right\}$ (I do not know if that approximation is superior or inferior, in the case of $(I)$ we knew that it was superior since we choose $\varepsilon$ such that $\mathbb{P}_{true}\in \mathcal{B}_{\varepsilon}^{p}(\widehat{\mathbb{P}}_{N})$). I would like to recreate in the problem $(II)$ the techniques used to treat the problem $(I)$, precisely in that way I have found ($\bigstar$).

• Do you know the answer for $N=1$? – Dirk Jan 4 '18 at 20:07
• What do you mean by "explicitly calculate"? Obtain as an elementary function of $p,N,x,h,\lambda$? – Iosif Pinelis Jan 4 '18 at 21:28
• @Dirk I have edited my post with an addendum, I hope this addendum answers your question. – matematicaActiva Jan 5 '18 at 17:58
• @IosifPinelis I have edited my post with an addendum, I hope this addendum answers your question. – matematicaActiva Jan 5 '18 at 17:58