A Sparse Multi-Scale Algorithm for Dense Optimal Transport

Understand

Discrete optimal transport solvers do not scale well on dense large problems since they do not explicitly exploit the geometric structure of the cost function.

• In analogy to continuous optimal transport we provide a framework to verify global optimality of a discrete transport plan locally.
• This allows construction of an algorithm to solve large dense problems by considering a sequence of sparse problems instead.
• The algorithm lends itself to being combined with a hierarchical multi-scale scheme.