Solving a quadratic 1D optimal transport problem just consists in sorting two measures and assigning the mass accordingly. If we consider atomic measures made of at most N masses, this just takes O(N log(N)). Thus, it would be great to be able to solve an n-dimensional optimal transport problem just by solving a small number of 1D problems. But this does not seem plausible. However, we'll see (experimentally) how effective this idea can be if we just ask for a reasonnably good transport. We'll also discuss some heuristics that can explain the efficiency of some of these approaches.
Copyright. All Rights Reserved.