On Robust Optimal Transport: Computational Complexity and Barycenter
  Computation
  We consider robust variants of the standard optimal transport, named robust
optimal transport, where marginal constraints are relaxed via Kullback-Leibler
divergence. We show that Sinkhorn-based algorithms can approximate the optimal
cost of robust optimal transport in
$\widetilde{\mathcal{O}}(\frac{n^2}{\varepsilon})$ time, in which $n$ is the
number of supports of the probability distributions and $\varepsilon$ is the
desired error. Furthermore, we investigate a fixed-support robust barycenter
problem between $m$ discrete probability distributions with at most $n$ number
of supports and develop an approximating algorithm based on iterative Bregman
projections (IBP). For the specific case $m = 2$, we show that this algorithm
can approximate the optimal barycenter value in
$\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon})$ time, thus being better
than the previous complexity
$\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon^2})$ of the IBP algorithm for
approximating the Wasserstein barycenter.
