4
$\begingroup$

Let $\mu$ & $\nu$ be a pair of discrete probability measures on $\mathbb{R}^d$ defined by

$$\mu = \frac{1}{n}\sum_{i=1}^n \delta_{x_i} \quad ;\quad \nu= \frac{1}{n}\sum_{i=1}^n \delta_{y_i}$$

where $x_i, y_i \in \mathbb{R}^d$. We can think of $\mu$ and $\nu$ as denoting two distributions of $n$ shipping crates on $\mathbb{R}^d$ where crates have equal mass and can be stacked on top of one another. I want to find an algorithm to compute the Wasserstein distance between $\mu$ and $\nu$. The Wasserstein distance is given by

$$ W_p(\mu,\nu) = \min_{\sigma \in S_n} \left\{ \frac{1}{n} \sum_{i=1}^n |x_i-y_{\sigma(i)} |^p \right\}. \hskip20pt (*)$$

I.e. The Wasserstein distance gives the minimum cost necessary to move all crates from distribution $\mu$ to distribution $\nu$, where the cost for moving a crate from $x$ to $y$ in this case is $\frac{1}{n}|x - y|^p$. See e.g. Villani - Topics in Optimal Transport Theory, page 5.

The minimizer clearly exists because $S_n$ is finite, but (at least naively) it seems to be difficult to compute in practice because $|S_n| = n!$. Looking online I find some hints that the problem might be solvable in polynomial time, but I become stooped in complicated general theory which does not immediately seem to apply to this problem. I am not familiar with either optimal transport theory or optimization. I am most interested in the case $p=1$, though the cases $p\in(1,\infty)$ are also of interest.

Can anyone provide either:

(i) An account of existing theory/algorithms for computing (*), ideally in the case $p=1$ but also possibly for general $p\in[1,\infty)$, or

(ii) Some clear references covering (i).

Many thanks! A.

$\endgroup$

1 Answer 1

3
$\begingroup$

In your case this could be seen as an instance of the Assignment Problem, which you can solve using the Hungarian Method in $\mathcal{O}(n^3)$.

$\endgroup$
4
  • $\begingroup$ Great :) I had not known about the assigment problem, so that is really helpful! One point that I observe though is that the assignment problem asks to find the optimal solution (i.e. the optimal $\sigma$, which may also be non-unique), whereas in my case I only need to find the optimal cost (which could in theory be known without knowledge of sigma). Thus, at least a priori, my problem seems simpler than the assignment problem. So one may even hope for faster algorithms that $\mathcal{O}(n^3)$ in this case. Do you know of any work around this? $\endgroup$ May 6, 2020 at 8:58
  • 1
    $\begingroup$ I’m not sure, but if your solution doesn’t need to be exact, you can look into approximations such as Entropy-Regularized Wasserstein Distance or if applicable to your problem Convolutional Wasserstein Distance, or others. See for example Computational Optimal Transport or Solomon et al, and look at some pretty pictures too! :) $\endgroup$
    – dirich1337
    May 6, 2020 at 11:08
  • 1
    $\begingroup$ @Aerinmund Fagelson Pretty much the same question by me, and answer or-exchange.org/questions/12391/… . That forum is now read only. And has essentially moved to or.stackexchange.com , where you should feel free to ask again (linking to this Mathematics Stack Exxhange question). $\endgroup$ May 6, 2020 at 15:18
  • $\begingroup$ Great! Thank-you dirich1337 and Mark L. Stone. Taken together that completely answers my question :) $\endgroup$ May 7, 2020 at 8:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .