×

Fast transport optimization for Monge costs on the circle. (English) Zbl 1229.90088

Let \(\hat{\mu}_{0}\) and \(\hat{\mu}_{1}\) be two probability measures on the unit circle \(\mathbb{T=R}/\mathbb{Z}\) and \(\hat{c}\left( \hat{x},\hat{y} \right) \) a given cost of transporting a unit mass from \(\hat{x}\) to \(\hat{y} \) in \(\mathbb{T}\). The transport cost is defined as the infimum of the quantity \[ \hat{I}\left( \gamma \right) =\int \int_{\mathbb{T\times T}}\hat{c}\left( \hat{x},\hat{y}\right) \gamma \left( \mathrm{d}\hat{x}\times \mathrm{d}\hat{y }\right) (1) \] over the set of all couplings \(\gamma \) of the probability measures \(\hat{\mu }_{0}\) and \(\hat{\mu}_{1}.\)
In this paper, the authors present an efficient algorithm for transport optimization on the circle.
It is shown that the problem of minimizing the integral (1) can be replaced with the “minimization” of the integral \[ I\left( \gamma \right) =\int \int_{\mathbb{T\times T}}c\left( x,y\right) \gamma \left( \mathrm{d}x\times \mathrm{d}y\right) ,(2) \] where the cost function satisfies the Monge condition \[ c\left( x_{1},y_{1}\right) +c\left( x_{2},y_{2}\right) <c\left( x_{1},y_{2}\right) +c\left( x_{2},y_{1}\right) \] for all \(x_{1}<x_{2}\) and \(y_{1}<y_{2}.\)
The authors introduce the notion of a locally optimal transport plan and show that all locally optimal transport plans are conjugate to shifts and that the cost of a locally optimal transport plan is a convex function of a shift parameter.
A fast algorithm for transport optimization on a circle is also presented together with a few numerical experiments. Finally, a review of related work in the computer science literature is given.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C25 Convex programming
68Q25 Analysis of algorithms and problem complexity

Software:

EMD
PDFBibTeX XMLCite
Full Text: DOI arXiv