Fast Algorithms for a New Relaxation of Optimal Transport

We introduce a new class of objectives for optimal transport computations of datasets in high-dimensional Euclidean spaces. The new objectives are parametrized by ρ ≥ 1, and provide a metric space Rρ(·, ·) for discrete probability distributions in ℝd. As ρ approaches 1, the metric approaches the Earth Mover's distance, but for ρ larger than (but close to) 1, admits significantly faster algorithms. Namely, for distributions μ and nu supported on n and m vectors in ℝd of norm at most r and any ε > 0, we give an algorithm which outputs an additive ε r-approximation to Rρ(μ, nu) in time (n+m) · poly((nm)(ρ-1)/ρ · 2ρ / (ρ-1) / ε).