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}$
Best Answer
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.