Discrete Optimal Transport: Complexity, Geometry and Applications

Abstract

In this article, we introduce a new algorithm for solving discrete optimal transport based on iterative resolutions of local versions of the dual linear program. We show a quantitative link between the complexity of this algorithm and the geometry of the underlying measures in the quadratic Euclidean case. This discrete method is then applied to investigate two optimal transport problems with geometric flavor: the regularity of optimal transport plan on oblate ellipsoids, and Alexandrov’s problem of reconstructing a convex set from its Gaussian measure.

Appendix: Convergence of the Sequence of Linearized Problems

In this section, we prove the global convergence of the sequence of linearized problems considered in Sect. 3.2. We freely reuse notation from this section. The following easy lemma shows that (P2$_{w}^{\varepsilon }$) is indeed a localization of (P2).

Lemma 6.1

Any pair of vectors $(v, w+\delta )$ which satisfies the constraints of the localized problem P2$_{w}^{\varepsilon }$ also satisfy the constraints of (P2).

Proof of Lemma 6.1

Fix a point x in X, and order the points in Y by increasing values of $w(y) + c(x,y)$, i.e.

$$\begin{aligned} w(y_1) + c(x,y_1) \leqslant w(y_2) + c(x,y_2) \leqslant \cdots \end{aligned}$$

Now, consider a point $y \in Y$ such that (x, y) does not belong to $\mathrm {G}_\varepsilon (w)$, i.e. such that

$$\begin{aligned} w(y) + c(x,y) > \min _{z\in Y} w(z) + c(x,z) + \varepsilon = c(x,y_1) + w(y_1) + \varepsilon . \end{aligned}$$

Using this inequality, we have

$$\begin{aligned} v(x) - (w(y)+\delta (y)) < v(x) + c(x,y) - (c(x,y_1) + w(y_1) + \varepsilon + \delta (y)). \end{aligned}$$

Since the pair of vectors $(v, w+\delta )$ satisfies the constraints of (P2$_{w}^{\varepsilon }$), we know that $v(x) - w(y_1) - c(x,y_1) \leqslant \delta (y_1)$ and

$$\begin{aligned} v(x) - (w(y)+\delta (y)) \leqslant c(x,y) + \delta (y_1) - \delta (y) - \varepsilon . \end{aligned}$$

Using the fact that $\delta (y_1)$ and $\delta (y)$ belong to $[0,\varepsilon ]$, we see that the pair $(v, w+\delta )$ also satisfies all the constraints of (P2). $\square$

Proof of Proposition 3.1

By the previous lemma, any maximizer $(v, w+\delta )$ of (P2$_{w}^{\varepsilon }$) is admissible for the problem (P2). If for every point y  the value of $\delta (y)$ belongs to $(0,\varepsilon )$, this pair satisfies the same optimality conditions as optimal vectors of Problem (P2). Thus, w it is a global maximizer of (P3) by concavity. $\square$

Proof of Proposition 3.2

Let $y_0$ be a point in Y, and consider $E = \{ w: Y\rightarrow \mathbb {R}; w(y_0) = 0 \}.$ A sequence of iterates $(w_i)$ of the algorithm determines a sequence $(v_i)$ in E by setting $v_i = v_i - w_i(y_0)$. Lemma 6.1 then implies that

$$\begin{aligned} \Phi (v_i) = \Phi (w_{i+1}) \geqslant \max \left\{ \Phi (v);~ v\in B_i \right\} , \end{aligned}$$

where $B_i$ is the $\ell ^\infty$ ball $B_i = v_i+[-\frac{\varepsilon }{2}; \frac{\varepsilon }{2}]^M$ and $\Phi$ is the function defined in (P3). The restriction of $\Phi$ to E is concave, piecewise-linear and coercive, and we consider its (compact) set of maximizers $F_0 = \arg \max _{E} \Phi$. Since the number of facets on which $\Phi$ is piecewise-linear is finite, there exists a positive number $\delta$ such that

$$\begin{aligned} \min \{ \left\| \nabla \left. \Phi \right| _{E}(v)\right\| ; v\in E\setminus F_0 \} > \delta . \end{aligned}$$

(5.4)

We now consider the ith iteration of the algorithm, in which we construct $v_{i+1}$ from $v_i$. If the ball $B_i$ intersects $F_0$, $v_{i+1}$ is a global maximizer of $\Phi$ by definition. If not, we can use the lower bound (5.4) on the norm of $\nabla \Phi$ to show that $\Phi (w_{i+1})$ has increased by some uniform constant. This can be seen by setting

$$\begin{aligned} \left\{ \begin{aligned}&v(0) = v_i, \\&v'(t) = \frac{\nabla \Phi (v(t))}{\left\| \nabla \Phi (v(t))\right\| } \end{aligned}\right. , \end{aligned}$$

where we assumed $\Phi$ smooth to simplify the argument. The curve v has unit speed and cannot leave $B_i$ before time $T = \varepsilon /2$, giving us

$$\begin{aligned} \Phi (v_{i+1}) = \Phi (v_i) + \int _0^T {\left\| \nabla \Phi (v(t))\right\| } \mathrm{d}t \geqslant \Phi (v_i) + \frac{\varepsilon }{2} \delta . \end{aligned}$$

We get the lower bound $\Phi (w_{i+1}) \geqslant \Phi (w_0) + (i+1)\frac{\varepsilon }{2}\delta$ at each step before convergence, implying convergence in a finite number of steps. $\square$