Wasserstein barycenters are NP-hard to compute
Wasserstein barycenters are NP-hard to compute
复制标题
Wasserstein 重心是 NP 难计算的
DOI：
10.1137/21m1390062
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Enric Boix
中科院分区：
文献类型：
--
作者：
Jason M. Altschuler;Enric Boix
计算Wasserstein质心（又称最优输运质心）是几何中的一个基本问题，近年来由于在数据科学中的许多应用而引起了相当大的关注。虽然在任何固定维度上都存在多项式时间算法，但所有已知的运行时间在维度上都受到指数级的影响。这种指数相关性是否可以改进为多项式相关性是一个有待解决的问题。本文证明了除非P=NP，否则答案是否定的。这揭示了Wasserstein质心计算的“维度诅咒”，而这种诅咒不会发生在最优传输计算中。此外，我们计算Wasserstein质心的硬度结果扩展到近似计算，到看似简单的问题情况，以及在其他最优传输度量中平均概率分布。
Computing Wasserstein barycenters (a.k.a. Optimal Transport barycenters) is a fundamental problem in geometry which has recently attracted considerable attention due to many applications in data science. While there exist polynomial-time algorithms in any fixed dimension, all known running times suffer exponentially in the dimension. It is an open question whether this exponential dependence is improvable to a polynomial dependence. This paper proves that unless P=NP, the answer is no. This uncovers a"curse of dimensionality"for Wasserstein barycenter computation which does not occur for Optimal Transport computation. Moreover, our hardness results for computing Wasserstein barycenters extend to approximate computation, to seemingly simple cases of the problem, and to averaging probability distributions in other Optimal Transport metrics.
具有树结构成本的多边际最优传输和薛定谔桥问题
影响因子：
2.2
作者：
Haasler, Isabel;Ringh, Axel;Chen, Yongxin;Karlsson, Johan
通讯作者：
Karlsson, Johan
影响因子：
2.5
作者：
Haasler, Isabel;Singh, Rahul;Chen, Yongxin
通讯作者：
Chen, Yongxin