Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm

We study the fixed-support Wasserstein barycenter problem (FS-WBP), which consists in computing the Wasserstein barycenter of m discrete probability measures supported on a finite metric space of size n. We show first that the constraint matrix arising from the standard linear programming (LP) representation of the FS-WBP is not totally unimodular when m ≥ 3 and n ≥ 3. This result resolves an open question pertaining to the relationship between the FS-WBP and the minimum-cost flow (MCF) problem since it proves that the FS-WBP in the standard LP form is not an MCF problem when m ≥ 3 and n ≥ 3. We also develop a provably fast deterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named FastIBP, with a complexity bound of O(mn 7/3 ε -4/3 ), where ε ∈ (0, 1) is the desired tolerance. This complexity bound is better than the best known complexity bound of O(mn 2 ε -2 ) for the IBP algorithm in terms of ε, and that of O(mn 5/2 ε -1 ) from accelerated alternating minimization algorithm or accelerated primaldual adaptive gradient algorithm in terms of n. Finally, we conduct extensive experiments with both synthetic data and real images and demonstrate the favorable performance of the FastIBP algorithm in practice. that capture the computational hardness of these problems [Peyré and Cuturi, 2019] . For the OT problem, Cuturi [2013] introduced the Sinkhorn algorithm which has triggered significant progress [