论文标题
最佳运输问题的力矩SOS方法
Moment-SoS Methods for Optimal Transport Problems
论文作者
论文摘要
目前，最常见的最佳运输（OT）求解器是基于通过离散措施对基本措施的近似。但是，有时只能使用措施时刻而不是措施本身工作，并且许多常见的OT问题可以作为力矩问题提出（最相关的例子是$ l^p $ -Wasserstein距离，Barycenters，Barycenters和Gromov-Wasserstein差异在Euclidean空间上差异）。我们利用这一事实来开发涵盖这些OT问题类别的广义力矩表述。运输计划以给定的时刻为代表，边缘约束以矩限制表示。然后，一个实用的计算在于考虑到一定顺序的相关力矩序列的截断，并使用多项式按等级层次结构进行半代数集的措施。我们证明，随着顺序增加，该策略会收敛到OT问题的解决方案。我们还展示了如何使用ChristOffel-Darboux内核从计算的矩中估算最佳传输图的支持，以及如何估算最佳传输图的支持。数值实验说明了方法的良好行为。
Most common Optimal Transport (OT) solvers are currently based on an approximation of underlying measures by discrete measures. However, it is sometimes relevant to work only with moments of measures instead of the measure itself, and many common OT problems can be formulated as moment problems (the most relevant examples being $L^p$-Wasserstein distances, barycenters, and Gromov-Wasserstein discrepancies on Euclidean spaces). We leverage this fact to develop a generalized moment formulation that covers these classes of OT problems. The transport plan is represented through its moments on a given basis, and the marginal constraints are expressed in terms of moment constraints. A practical computation then consists in considering a truncation of the involved moment sequences up to a certain order, and using the polynomial sums-of-squares hierarchy for measures supported on semi-algebraic sets. We prove that the strategy converges to the solution of the OT problem as the order increases. We also show how to approximate linear quantities of interest, and how to estimate the support of the optimal transport map from the computed moments using Christoffel-Darboux kernels. Numerical experiments illustrate the good behavior of the approach.
