Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers

Wasserstein Barycenter（WB）是最基本的最优输运问题之一。给定一组分布，WB的目标是找到一个新分布，使其与这些分布的平均Wasserstein距离最小化。如果我们将解限制为“$k$-sparse”，则问题变得更加困难。本文研究了存在离群值的$k$-sparse WB问题，这是一个更实际的设置，因为现实世界的数据经常包含噪声。现有的WB算法无法直接扩展到处理具有离群值的情况，因此迫切需要开发一些新的想法。首先，我们研究了$k$-sparse WB与聚类（带有离群值）问题之间的关系。特别地，我们提出了一种基于聚类的LP方法，该方法为带有离群值的$k$-sparse WB问题提供了常数近似因子。此外，如果维度不高，我们利用核心集技术实现$(1+\epsilon)$-近似因子，其中$\epsilon>0$。最后，我们对我们提出的算法进行实验，并说明它们在实践中的效率。

解决问题：本论文研究带有离群值的稀疏Wasserstein Barycenter问题，探究其与聚类问题的关系，并提出了一种基于聚类的LP方法和一种基于coreset技术的算法。

关键思路：本论文提出了一种基于聚类的LP方法，可为带有离群值的稀疏Wasserstein Barycenter问题提供常数逼近因子；此外，还提出了一种基于coreset技术的算法，可在维度不高的情况下实现任意ε>0的(1+ε)逼近因子。

其他亮点：本论文的实验设计充分，使用了多个数据集进行验证，并且提供了开源代码。值得进一步深入研究的工作包括如何将方法扩展到更高维度的情况下，并且探索更多的离群值处理方法。

相关研究：最近在这个领域中，还有一些相关的研究，包括《A sparse optimal transport algorithm for domain adaptation》和《Outlier-robust low-rank subspace tracking》等。