Name
Abstract | ||
|---|---|---|
Our goal is to solve the large-scale linear programming (LP) formulation of Optimal Transport (OT) problems efficiently. Our key observations are: (i) the primal solutions of the LP problems are theoretically very sparse; (ii) the cost function is usually equipped with good geometric properties. The former motivates us to eliminate the majority of the variables, while the latter easily enables us to exploit a hierarchical multiscale structure. Each level in this structure corresponds to a standard OT problem, whose solution can be obtained by solving a series of restricted OT problems by fixing most of the primal variables to zeros and using the semi-smooth Newton method. We improve the performance of computing the semi-smooth Newton direction by forming and solving a much smaller symmetric positive-definite system whose matrix can be written explicitly according to the sparsity patterns. Extensive numerical experiments show that our algorithm is quite efficient compared to the state-of-the-art methods such as a multiscale implementation of the CPLEX’s Networkflow algorithm and the SparseSinkhorn method, due to its ability to solve problems at a much larger scale and obtain the optimal solution in less time. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s10915-022-01813-y | Journal of Scientific Computing |
Keywords | DocType | Volume |
Optimal transport, Sparsity, Semi-smooth Newton method, Multiscale structure, 15A03, 65F10, 65K05, 90C05 | Journal | 91 |
Issue | ISSN | Citations |
2 | 0885-7474 | 0 |
PageRank | References | Authors |
0.34 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yiyang Liu | 1 | 0 | 0.34 |
| Zaiwen Wen | 2 | 934 | 40.20 |
| Wotao Yin | 3 | 5038 | 243.92 |