论文标题
自由支持的简单近似算法
Simple Approximative Algorithms for Free-Support Wasserstein Barycenters
论文作者
论文摘要
由于其在数据科学中的广泛应用，离散措施的计算瓦斯汀重中心最近引起了广泛的关注。通常，这个问题是NP-HARD，要求使用实用的近似算法。在本文中，我们分析了一个众所周知的简单框架，用于近似wasserstein- $ p $ barycenters，我们主要认为最常见的情况$ p = 2 $和$ p = 1 $，这不是很好的讨论。该框架会产生稀疏的支持解决方案，并在自由支持设置中显示出良好的数值结果。根据所需的准确性水平，这仅需要$ n-1 $或$ n（n-1）/2 $标准的两分边界最佳运输（OT）计算，分别是$ n $输入度量，即快速，存储器效率且易于使用任何OT Solver用作黑匣子。此外，这些方法的相对错误最多为$ n $和$ 2 $，同时$ p = 1，2 $。我们证明这些界限实际上是锋利的。鉴于问题的硬度，这种保证总体上不能接近最佳性，这不足为奇。然而，对于给定的特定问题，这些误差范围通常会大大降低，并且可以在几乎没有计算开销的情况下进行评估，尤其是在没有最佳解决方案的情况下。在我们的数值实验中，这保证了最多百分之几的错误。
Computing Wasserstein barycenters of discrete measures has recently attracted considerable attention due to its wide variety of applications in data science. In general, this problem is NP-hard, calling for practical approximative algorithms. In this paper, we analyze a well-known simple framework for approximating Wasserstein-$p$ barycenters, where we mainly consider the most common case $p=2$ and $p=1$, which is not as well discussed. The framework produces sparse support solutions and shows good numerical results in the free-support setting. Depending on the desired level of accuracy, this requires only $N-1$ or $N(N-1)/2$ standard two-marginal optimal transport (OT) computations between the $N$ input measures, respectively, which is fast, memory-efficient and easy to implement using any OT solver as a black box. What is more, these methods yield a relative error of at most $N$ and $2$, respectively, for both $p=1, 2$. We show that these bounds are practically sharp. In light of the hardness of the problem, it is not surprising that such guarantees cannot be close to optimality in general. Nevertheless, these error bounds usually turn out to be drastically lower for a given particular problem in practice and can be evaluated with almost no computational overhead, in particular without knowledge of the optimal solution. In our numerical experiments, this guaranteed errors of at most a few percent.
