论文标题
可以在多项式时间内在固定维度中计算出瓦斯坦的barycenter
Wasserstein barycenters can be computed in polynomial time in fixed dimension
论文作者
论文摘要
计算瓦斯汀·巴里中心（Barycenters）是机器学习，统计和计算机图形中广泛应用的基本几何问题。但是，尚不清楚Wasserstein Barycenter是否可以在多项式时间（即精确或高精度）计算（即使用$ \ textrm {polylog}（1/\ varepsilon）$运行时依赖性）。本文以肯定地回答了这些问题。我们的方法是通过使用计算几何形状的技术有效实现相应的分离甲骨文来解决指数尺寸的线性编程公式。
Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whether Wasserstein barycenters can be computed in polynomial time, either exactly or to high precision (i.e., with $\textrm{polylog}(1/\varepsilon)$ runtime dependence). This paper answers these questions in the affirmative for any fixed dimension. Our approach is to solve an exponential-size linear programming formulation by efficiently implementing the corresponding separation oracle using techniques from computational geometry.
