We provide theoretical analyses for two algorithms that solve the regularized
optimal transport (OT) problem between two discrete probability measures with
at most $n$ atoms. We show that a greedy variant of the classical Sinkhorn
algorithm, known as the \emph{Greenkhorn algorithm}, can be improved to
$\widetilde{\mathcal{O}}(n^2\varepsilon^{-2})$, improving on the best known
complexity bound of $\widetilde{\mathcal{O}}(n^2\varepsilon^{-3})$. Notably,
this matches the best known complexity bound for the Sinkhorn algorithm and
helps explain why the Greenkhorn algorithm can outperform the Sinkhorn
algorithm in practice. Our proof technique, which is based on a primal-dual
formulation and a novel upper bound for the dual solution, also leads to a new
class of algorithms that we refer to as \emph{adaptive primal-dual accelerated
mirror descent} (APDAMD) algorithms. We prove that the complexity of these
algorithms is $\widetilde{\mathcal{O}}(n^2\sqrt{\delta}\varepsilon^{-1})$,
where $\delta > 0$ refers to the inverse of the strong convexity module of
Bregman divergence with respect to $\|\cdot\|_\infty$. This implies that the
APDAMD algorithm is faster than the Sinkhorn and Greenkhorn algorithms in terms
of $\varepsilon$. Experimental results on synthetic and real datasets
demonstrate the favorable performance of the Greenkhorn and APDAMD algorithms
in practice.

我们提供两种算法的理论分析，这两种算法可以解决两个离散概率测度之间的规则化最优输运问题，我们证明了一种名为绿角（Greenkhorn）算法的贪心版本可以改进到 O˜（n²ε ^-2），这种算法可以在实践中击败 Sinkhorn 算法，基于这个理论我们提出了新的算法。

高效最优输运：贪婪算法和加速镜像下降算法分析

On Efficient Optimal Transport: An Analysis of Greedy and Accelerated  Mirror Descent Algorithms

We introduce a novel family of invariant, convex, and non-quadratic
functionals that we employ to derive regularized solutions of ill-posed linear
inverse imaging problems. The proposed regularizers involve the Schatten norms
of the Hessian matrix, computed at every pixel of the image. They can be viewed
as second-order extensions of the popular total-variation (TV) semi-norm since
they satisfy the same invariance properties. Meanwhile, by taking advantage of
second-order derivatives, they avoid the staircase effect, a common artifact of
TV-based reconstructions, and perform well for a wide range of applications. To
solve the corresponding optimization problems, we propose an algorithm that is
based on a primal-dual formulation. A fundamental ingredient of this algorithm
is the projection of matrices onto Schatten norm balls of arbitrary radius.
This operation is performed efficiently based on a direct link we provide
between vector projections onto $\ell_q$ norm balls and matrix projections onto
Schatten norm balls. Finally, we demonstrate the effectiveness of the proposed
methods through experimental results on several inverse imaging problems with
real and simulated data.

提出一个新的方法，将 Schatten 范数的 Hessian 矩阵应用于正则化解决线性反演成像问题，并通过原始 - 对偶算法进行求解，该方法在实验中证明在应对多种真实和模拟数据的情况下表现良好。