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 $\rho \ge 1$, and provide a metric space ${\mathcal{R}}_{\rho }(\cdot ,\cdot )$ for discrete probability distributions in ${\mathbb{R}}^d$. As $\rho$ approaches $1$, the metric approaches the Earth Mover’s distance, but for $\rho$ larger than (but close to) $1$, admits significantly faster algorithms. Namely, for distributions $\mu$ and $\nu$ supported on $n$ and $m$ vectors in ${\mathbb{R}}^d$ of norm at most $r$ and any $\epsilon >0$, we give an algorithm which outputs an additive $\epsilon r$-approximation to ${\mathcal{R}}_{\rho }(\mu ,\nu )$ in time $(n+m)\cdot \mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}((nm{)}^{(\rho -1)\mathrm{/}\rho }\cdot 2^{\rho \mathrm{/}(\rho -1)}\mathrm{/}\epsilon )$.