2018/09/12 by Jia Li, Yang, Lei, Li, Jia +5 · 1 citation
Computer Science · Engineering · #Advanced Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Fluid Dynamics and Turbulent Flows #Image and Signal Denoising Methods #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1809.04249
openalex publication_date 2018/09/12 · openalex created_date 2021/02/15 · openalex updated_date 2026/07/28
We consider the problem of computing a Wasserstein barycenter for a set of\ndiscrete probability distributions with finite supports, which finds many\napplications in areas such as statistics, machine learning and image\nprocessing. When the support points of the barycenter are pre-specified, this\nproblem can be modeled as a linear programming (LP) problem whose size can be\nextremely large. To handle this large-scale LP, we analyse the structure of its\ndual problem, which is conceivably more tractable and can be reformulated as a\nwell-structured convex problem with 3 kinds of block variables and a coupling\nlinear equality constraint. We then adapt a symmetric Gauss-Seidel based\nalternating direction method of multipliers (sGS-ADMM) to solve the resulting\ndual problem and establish its global convergence and global linear convergence\nrate. As a critical component for efficient computation, we also show how all\nthe subproblems involved can be solved exactly and efficiently. This makes our\nmethod suitable for computing a Wasserstein barycenter on a large-scale data\nset, without introducing an entropy regularization term as is commonly\npracticed. In addition, our sGS-ADMM can be used as a subroutine in an\nalternating minimization method to compute a barycenter when its support points\nare not pre-specified. Numerical results on synthetic data sets and image data\nsets demonstrate that our method is highly competitive for solving large-scale\nWasserstein barycenter problems, in comparison to two existing representative\nmethods and the commercial software Gurobi.\n