Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution

Understand

Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard.

• Even though such problems are ubiquitous in statistics, machine learning and computer vision, however, this perception has not yet received a theoretical justification.
• To fill this gap, we prove that computing the Wasserstein distance between a discrete probability measure supported on two points and the Lebesgue measure on the standard hypercube is already #P-hard.
• This insight prompts us to seek approximate solutions for semi-discrete optimal transport problems.