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 textitnot 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 textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP, with a complexity bound of tildeO(mn7/3varepsilon-4/3), where varepsilon ∈ (0, 1) is the desired tolerance. This complexity bound is better than the best known complexity bound of tildeO(mn2varepsilon-2) for the IBP algorithm in terms of varepsilon, and that of tildeO(mn5/2varepsilon-1) from accelerated alternating minimization algorithm or accelerated primal-dual 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 textscFastIBP algorithm in practice.