Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/93925
DC Field | Value | Language |
---|---|---|
dc.contributor | Department of Applied Mathematics | en_US |
dc.creator | Yang, L | en_US |
dc.creator | Li, J | en_US |
dc.creator | Sun, D | en_US |
dc.creator | Toh, KC | en_US |
dc.date.accessioned | 2022-08-03T01:24:14Z | - |
dc.date.available | 2022-08-03T01:24:14Z | - |
dc.identifier.issn | 1532-4435 | en_US |
dc.identifier.uri | http://hdl.handle.net/10397/93925 | - |
dc.language.iso | en | en_US |
dc.publisher | MIT Press | en_US |
dc.rights | © 2021 Lei Yang, Jia Li, Defeng Sun and Kim-Chuan Toh. | en_US |
dc.rights | License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v22/19-629.html. | en_US |
dc.rights | The following publication Yang, L., Li, J., Sun, D., & Toh, K. C. (2021). A fast globally linearly convergent algorithm for the computation of Wasserstein barycenters. The Journal of Machine Learning Research, 22(21), 1-37 is available at https://jmlr.org/papers/v22/19-629.html | en_US |
dc.subject | Wasserstein barycenter | en_US |
dc.subject | Discrete probability distribution | en_US |
dc.subject | Semi-proximalADMM | en_US |
dc.subject | Symmetric Gauss-Seidel | en_US |
dc.title | A fast globally linearly convergent algorithm for the computation of Wasserstein barycenters | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.spage | 1 | en_US |
dc.identifier.epage | 37 | en_US |
dc.identifier.volume | 22 | en_US |
dcterms.abstract | We consider the problem of computing a Wasserstein barycenter for a set of discrete probability distributions with finite supports, which finds many applications in areas such as statistics, machine learning and image processing. When the support points of the barycenter are pre-specified, this problem can be modeled as a linear programming (LP) problem whose size can be extremely large. To handle this large-scale LP, we analyse the structure of its dual problem, which is conceivably more tractable and can be reformulated as a well-structured convex problem with 3 kinds of block variables and a coupling linear equality constraint. We then adapt a symmetric Gauss-Seidel based alternating direction method of multipliers (sGS-ADMM) to solve the resulting dual problem and establish its global convergence and global linear convergence rate. As a critical component for efficient computation, we also show how all the subproblems involved can be solved exactly and efficiently. This makes our method suitable for computing a Wasserstein barycenter on a large-scale data set, without introducing an entropy regularization term as is commonly practiced. In addition, our sGS-ADMM can be used as a subroutine in an alternating minimization method to compute a barycenter when its support points are not pre-specified. Numerical results on synthetic data sets and image data sets demonstrate that our method is highly competitive for solving large-scale Wasserstein barycenter problems, in comparison to two existing representative methods and the commercial software Gurobi. | en_US |
dcterms.accessRights | open access | en_US |
dcterms.bibliographicCitation | Journal of machine learning research, 2021, v. 22, 21, p. 1-37 | en_US |
dcterms.isPartOf | Journal of machine learning research | en_US |
dcterms.issued | 2021 | - |
dc.identifier.eissn | 1533-7928 | en_US |
dc.identifier.artn | 21 | en_US |
dc.description.validate | 202208 bcfc | en_US |
dc.description.oa | Version of Record | en_US |
dc.identifier.FolderNumber | AMA-0087 | - |
dc.description.fundingSource | Others | en_US |
dc.description.fundingText | PolyU | en_US |
dc.description.pubStatus | Published | en_US |
dc.identifier.OPUS | 54170923 | - |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
19-629.pdf | 827.98 kB | Adobe PDF | View/Open |
Page views
62
Last Week
0
0
Last month
Citations as of May 12, 2024
Downloads
13
Citations as of May 12, 2024
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.