2020/02/12 by Tianyi Lin, Lin, Tianyi, Nhat Ho +7 · 1 citation
Engineering · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Geometric Analysis and Curvature Flows #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2002.04783
openalex publication_date 2020/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(mn7/3ε-4/3), where ε ∈ (0, 1) is the desired tolerance. This complexity bound is better than the best known complexity bound of O(mn2ε-2) for the IBP algorithm in terms of ε, and that of O(mn5/2ε-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 FastIBP algorithm in practice.