Linear programming of the Sinkhorn distance (entropy-regularized optimal transport)

110 Views Asked by At

\begin{align} \mathcal{W}_\epsilon(\alpha, \beta) =& \min_{\pi\in \Pi(\alpha\beta)} \int c(x,y) \mathrm{d}\pi(x,y) + \epsilon H(\pi) \\ =& \min_{\pi\in \Pi(\alpha\beta)} \int c(x,y) \mathrm{d}\pi(x,y) + \epsilon \int \pi(x,y) \ln \pi(x,y) \end{align} How can the above formula for the Sinkhorn distance be expressed as a linear programming optimization problem?

Is the following correct?

$$\begin{array}{rrcl} \min_\mathbf{x} \ \mathbf{c}^\top \mathbf{x} + \epsilon \mathbf{x}^\top \ln \mathbf{x} \\ \mathrm{s.t.} \ \mathbf{A} \mathbf{x} = \ \mathbf{b} \\ \ \mathbf{x} \geq \ \mathbf{0} \end{array}$$

where $H(\pi) = \epsilon \mathbf{x}^\top \ln \mathbf{x}$ is the entropy term.