We investigate the problem of optimal transport in the so-called Kantorovich
form, i.e. given two Radon measures on two compact sets, we seek an optimal
transport plan which is another Radon measure on the product of the sets that
has these two measures as marginals and minimizes a certain cost function. We
consider quadratic regularization of the problem, which forces the optimal
transport plan to be a square integrable function rather than a Radon measure.
We derive the dual problem and show strong duality and existence of primal and
dual solutions to the regularized problem. Then we derive two algorithms to
solve the dual problem of the regularized problem: A Gauss-Seidel method and a
semismooth quasi-Newton method and investigate both methods numerically. Our
experiments show that the methods perform well even for small regularization
parameters. Quadratic regularization is of interest since the resulting optimal
transport plans are sparse, i.e. they have a small support (which is not the
case for the often used entropic regularization where the optimal transport
plan always has full measure).

研究正则化问题的对偶问题，提出了用高斯 - 塞德尔方法和半光滑拟牛顿方法解决的方案，实验证明这两种方法在小正则化参数下表现良好。

二次正则化最优输运

Quadratically regularized optimal transport

A new result in convex analysis on the calculation of proximity operators in
certain scaled norms is derived. We describe efficient implementations of the
proximity calculation for a useful class of functions; the implementations
exploit the piece-wise linear nature of the dual problem. The second part of
the paper applies the previous result to acceleration of convex minimization
problems, and leads to an elegant quasi-Newton method. The optimization method
compares favorably against state-of-the-art alternatives. The algorithm has
extensive applications including signal processing, sparse recovery and machine
learning and classification.

本文提出了一种计算特定尺度规范下近似算子的凸分析方法，并利用对偶问题的分段线性特性描述了一类函数的高效实现，之后将该方法应用于凸最小化问题加速中并得到了优雅的拟牛顿方法，该算法在信号处理、稀疏恢复和机器学习分类等领域中具有广泛应用，并与现有方案相比具有较高的性能。