Wang Junqi, Wang Pei, Shafto Patrick
Department of Math & CS, Rutgers University, Newark, NJ 07102, USA.
School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA.
Entropy (Basel). 2023 May 24;25(6):839. doi: 10.3390/e25060839.
Obtaining solutions to optimal transportation (OT) problems is typically intractable when marginal spaces are continuous. Recent research has focused on approximating continuous solutions with discretization methods based on i.i.d. sampling, and this has shown convergence as the sample size increases. However, obtaining OT solutions with large sample sizes requires intensive computation effort, which can be prohibitive in practice. In this paper, we propose an algorithm for calculating discretizations with a given number of weighted points for marginal distributions by minimizing the (entropy-regularized) Wasserstein distance and providing bounds on the performance. The results suggest that our plans are comparable to those obtained with much larger numbers of i.i.d. samples and are more efficient than existing alternatives. Moreover, we propose a local, parallelizable version of such discretizations for applications, which we demonstrate by approximating adorable images.
当边际空间是连续的时候，获得最优传输（OT）问题的解决方案通常是难以处理的。最近的研究集中在使用基于独立同分布采样的离散化方法来近似连续解，并且随着样本量的增加，这已显示出收敛性。然而，使用大样本量获得OT解需要大量的计算工作，这在实践中可能是令人望而却步的。在本文中，我们提出了一种算法，通过最小化（熵正则化的）瓦瑟斯坦距离并提供性能界限，来计算具有给定数量加权点的边际分布的离散化。结果表明，我们的方案与使用多得多的独立同分布样本获得的方案相当，并且比现有替代方案更有效。此外，我们为应用提出了这种离散化的局部可并行版本，我们通过近似可爱图像来进行演示。
