The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
This work addresses computational bottlenecks in optimal transport for practitioners needing efficient solutions for semi-discrete problems with various cost functions.
The authors introduce the boundary method for semi-discrete optimal transport, which reduces effective problem dimension and improves complexity. For p-norm costs with p in (1,∞), they provide convergence guarantees and algorithmic development, with experimental support for general cost functions.
We introduce a new technique, which we call the boundary method, for solving semi-discrete optimal transport problems with a wide range of cost functions. The boundary method reduces the effective dimension of the problem, thus improving complexity. For cost functions equal to a p-norm with p in (1,infinity), we provide mathematical justification, convergence analysis, and algorithmic development. Our testing supports the boundary method with these p-norms, as well as other, more general cost functions.