Fast Transport Optimization for Monge Costs on the Circle

Source abstract

Consider the problem of optimally matching two measures on the circle, or equivalently two periodic measures on $\mathbb{R}$, and suppose that the cost $c(x,y)$ of matching two points x, y satisfies the Monge condition: $c(x_1,y_1)+c(x_2,y_2)<c(x_1,y_2)+c(x_2,y_1)$ whenever $x_1<x_2$ and $y_1<y_2$. We introduce a notion of locally optimal transport plan, motivated by the weak KAM (Aubry–Mather) theory, 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. This theory is applied to a transportation problem arising in image processing: for two sets of point masses on the circle, both of which have the same total mass, find an optimal transport plan with respect to a given cost function c satisfying the Monge condition. In the circular case the sorting strategy fails to provide a unique candidate solution, and a naive approach requires a quadratic number of operations. For the case of N real-valued point masses we present an $O(N|\log\epsilon|)$ algorithm that approximates the optimal cost within $\epsilon$; when all masses are integer multiples of $1/M$, the algorithm gives an exact solution in $O(N\log M)$ operations.