1
$\begingroup$

What is the difference between these two different versions of the linear programming optimization set-up for optimal transport (OT)? how to reconcile them mathematically to show that they are equivalent?

OT Linear Programming #1

(Source) \begin{align*} \min_{\boldsymbol\Gamma} \quad & \langle\mathbf{C},\boldsymbol\Gamma \rangle = \sum_{ij}\mathbf{C}_{ij}\boldsymbol\Gamma_{ij} \\ \mathrm{s. t.} \quad & \boldsymbol\Gamma \mathbf{1} = \mathbf{\alpha} \\ &\boldsymbol\Gamma^{\top}\mathbf{1} = \mathbf{\beta} \end{align*}

  • $\boldsymbol C$ is the distance matrix, which contains elements$\Vert x - y \Vert$,
  • $\boldsymbol \Gamma$ is the transport matrix, which contains elements $\gamma(x,y)$,
  • $\alpha$ and $\beta$ are the source and target probability distributions, respectively, of variables $X$ and $Y$.

OT Linear Programming #2

(Source) $$ \begin{array}{rrcl} \min_{\mathbf{x}} \ & \mathbf{c}^T \mathbf{x} & & \ \\ \mathrm{s.t.} \ & \mathbf{A} \mathbf{x} & = & \ \mathbf{b} \\ \ & \mathbf{x} & \geq &\ \mathbf{0} \end{array}$$

  • $\mathbf{c}$ is a vectorization of the distance matrix $\boldsymbol C$,
  • $\mathbf{x}$ is a vectorization of the transport matrix $\boldsymbol\Gamma$,
  • while the source and target distributions are $\mathbf{b} = \begin{bmatrix} \alpha \\ \beta\end{bmatrix}$
$\endgroup$
  • 1
    $\begingroup$ The first version is how you naturally think about it in mathematical terms and write in papers. The second version is how you have to reformulate it to actually fit it into canonical LP form (and possibly feed into a solver). $\endgroup$ – Michal Adamaszek Nov 13 '20 at 12:57
  • $\begingroup$ about reconciling the two, how can it be shown that the constraints in version #1 are a rewording of the constraints in version #2? $\endgroup$ – develarist Nov 13 '20 at 13:00
1
$\begingroup$

To reconcile both, note that $\bf x$ is obtained by stacking the columns of $\bf \Gamma$. For the cost, $\bf c$ is obtained by stacking the columns of the cost matrix $\bf C$. Also, let $\mathbb I_n$ be an $n\times n$ identity matrix. Therefore, make: $$ {\bf A} = \begin{bmatrix} {\bf 1}_n^\top \otimes \mathbb I_m\\ \mathbb I_n \otimes {\bf 1}_m^\top \end{bmatrix} $$

Finally, the constraint ${\bf x}\geq 0$ is the same as the constraint that the transport plan $\bf \Gamma$ must be positive. This can be found in page 38 in the book Computational Optimal Transport, by Peyré and Cuturi. The pdf of the book is freely avaiable.

$\endgroup$
  • $\begingroup$ I know that Program #2 shown in the question appears in Computational optimal transport, but do you know if Program #1 does too, or if they make reference to it? $\endgroup$ – develarist Nov 20 '20 at 3:58
  • $\begingroup$ Yeah, this #1 formulation of the problem is actually much more present throughout the book, while the second one is just briefly mentioned. As you pointed out, most algorithms for solving LP use the second formulation, and that is the only reason (I guess), the authors actually show it. $\endgroup$ – Davi Barreira Nov 20 '20 at 14:31
  • $\begingroup$ if $\boldsymbol c$ contains distances $| x - y|$, how can I reconcile the fact that $\mathbf{b} = \begin{bmatrix} \alpha \\ \beta\end{bmatrix}$ is just a figurative representation of $\bar{\boldsymbol{b}} = \begin{bmatrix} \boldsymbol x \\ \boldsymbol y \end{bmatrix}$, where $\alpha$ is by definition $\boldsymbol x$, the source distribution, and $\beta$ is by definition $\boldsymbol y$, the target distribution? $\endgroup$ – develarist Nov 30 '20 at 16:28
  • 1
    $\begingroup$ If it’s 1D, then there is an actual Monge map, which is given by the composition of the CDF and the inverse CDf $\endgroup$ – Davi Barreira Dec 3 '20 at 18:59
  • 1
    $\begingroup$ For discrete cases you can hard code it. I answered in your question $\endgroup$ – Davi Barreira Dec 3 '20 at 21:59

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.