File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10915-024-02570-w
- Scopus: eid_2-s2.0-85196354717
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Article: Randomized Methods for Computing Optimal Transport Without Regularization and Their Convergence Analysis
Title | Randomized Methods for Computing Optimal Transport Without Regularization and Their Convergence Analysis |
---|---|
Authors | |
Keywords | 65C35 68W20 90C08 90C25 Convergence analysis Convex optimization Deep particle method Optimal transport Random block coordinate descent |
Issue Date | 1-Aug-2024 |
Publisher | Springer |
Citation | Journal of Scientific Computing, 2024, v. 100, n. 2 How to Cite? |
Abstract | The optimal transport (OT) problem can be reduced to a linear programming (LP) problem through discretization. In this paper, we introduced the random block coordinate descent (RBCD) methods to directly solve this LP problem. Our approach involves restricting the potentially large-scale optimization problem to small LP subproblems constructed via randomly chosen working sets. By using a random Gauss-Southwell-q rule to select these working sets, we equip the vanilla version of (RBCD0) with almost sure convergence and a linear convergence rate to solve general standard LP problems. To further improve the efficiency of the (RBCD0) method, we explore the special structure of constraints in the OT problems and leverage the theory of linear systems to propose several approaches for refining the random working set selection and accelerating the vanilla method. Inexact versions of the RBCD methods are also discussed. Our preliminary numerical experiments demonstrate that the accelerated random block coordinate descent (ARBCD) method compares well with other solvers including stabilized Sinkhorn’s algorithm when seeking solutions with relatively high accuracy, and offers the advantage of saving memory. |
Persistent Identifier | http://hdl.handle.net/10722/345692 |
ISSN | 2023 Impact Factor: 2.8 2023 SCImago Journal Rankings: 1.248 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Xie, Yue | - |
dc.contributor.author | Wang, Zhongjian | - |
dc.contributor.author | Zhang, Zhiwen | - |
dc.date.accessioned | 2024-08-27T09:10:32Z | - |
dc.date.available | 2024-08-27T09:10:32Z | - |
dc.date.issued | 2024-08-01 | - |
dc.identifier.citation | Journal of Scientific Computing, 2024, v. 100, n. 2 | - |
dc.identifier.issn | 0885-7474 | - |
dc.identifier.uri | http://hdl.handle.net/10722/345692 | - |
dc.description.abstract | The optimal transport (OT) problem can be reduced to a linear programming (LP) problem through discretization. In this paper, we introduced the random block coordinate descent (RBCD) methods to directly solve this LP problem. Our approach involves restricting the potentially large-scale optimization problem to small LP subproblems constructed via randomly chosen working sets. By using a random Gauss-Southwell-q rule to select these working sets, we equip the vanilla version of (RBCD0) with almost sure convergence and a linear convergence rate to solve general standard LP problems. To further improve the efficiency of the (RBCD0) method, we explore the special structure of constraints in the OT problems and leverage the theory of linear systems to propose several approaches for refining the random working set selection and accelerating the vanilla method. Inexact versions of the RBCD methods are also discussed. Our preliminary numerical experiments demonstrate that the accelerated random block coordinate descent (ARBCD) method compares well with other solvers including stabilized Sinkhorn’s algorithm when seeking solutions with relatively high accuracy, and offers the advantage of saving memory. | - |
dc.language | eng | - |
dc.publisher | Springer | - |
dc.relation.ispartof | Journal of Scientific Computing | - |
dc.subject | 65C35 | - |
dc.subject | 68W20 | - |
dc.subject | 90C08 | - |
dc.subject | 90C25 | - |
dc.subject | Convergence analysis | - |
dc.subject | Convex optimization | - |
dc.subject | Deep particle method | - |
dc.subject | Optimal transport | - |
dc.subject | Random block coordinate descent | - |
dc.title | Randomized Methods for Computing Optimal Transport Without Regularization and Their Convergence Analysis | - |
dc.type | Article | - |
dc.identifier.doi | 10.1007/s10915-024-02570-w | - |
dc.identifier.scopus | eid_2-s2.0-85196354717 | - |
dc.identifier.volume | 100 | - |
dc.identifier.issue | 2 | - |
dc.identifier.eissn | 1573-7691 | - |
dc.identifier.issnl | 0885-7474 | - |