Multi‐to One‐Dimensional Optimal Transport

Source abstract

We consider the Monge‐Kantorovich problem of transporting a probability density on to another on the line, so as to optimize a given cost function. We introduce a nestedness criterion relating the cost to the densities, under which it becomes possible to solve this problem uniquely by constructing an optimal map one level set at a time. This map is continuous if the target density has connected support. We use level‐set dynamics to develop and quantify a local regularity theory for this map and the Kantorovich potentials solving the dual linear program. We identify obstructions to global regularity through examples. More specifically, fix probability densities f and g on open sets and with . Consider transporting f onto g so as to minimize the cost . We give a nondegeneracy condition on that ensures the set of x paired with [g‐a.e.] y ∈ Y lie in a codimension‐ n submanifold of X . Specializing to the case m > n = 1, we discover a nestedness criterion relating s to ( f,g ) that allows us to construct a unique optimal solution in the form of a map . When and g and f are bounded, the Kantorovich dual potentials ( u,υ ) satisfy , and the normal velocity V of with respect to changes in y is given by . Positivity of V locally implies a Lipschitz bound on f ; moreover, if intersects transversally. On subsets where this nondegeneracy, positivity, and transversality can be quantified, for each integer the norms of and are controlled by these bounds, , and the smallness of . We give examples showing regularity extends from $X to part of , but not from Y to . We also show that when s remains nested for all ( f,g ), the problem in reduces to a supermodular problem in . © 2017 Wiley Periodicals, Inc.