A Linear Complexity Algorithm for Optimal Transport Problem with Log-type Cost
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909548915195904 |
|---|---|
| author | Lyu, Ziyuan Wang, Zihao Wu, Hao Yang, Shuai |
| author_facet | Lyu, Ziyuan Wang, Zihao Wu, Hao Yang, Shuai |
| contents | In [Q. Liao et al., Commun. Math. Sci., 20(2022)], a linear-time Sinkhorn algorithm is developed based on dynamic programming, which significantly reduces the computational complexity involved in solving optimal transport problems. However, this algorithm is specifically designed for the Wasserstein-1 metric. We are curious whether the preceding dynamic programming framework can be extended to tackle optimal transport problems with different transport costs. Notably, two special kinds of optimal transport problems, the Sinkhorn ranking and the far-field reflector and refractor problems, are closely associated with the log-type transport costs. Interestingly, by employing series rearrangement and dynamic programming techniques, it is feasible to perform the matrix-vector multiplication within the Sinkhorn iteration in linear time for this type of cost. This paper provides a detailed exposition of its implementation and applications, with numerical simulations demonstrating the effectiveness and efficiency of our methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06578 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Linear Complexity Algorithm for Optimal Transport Problem with Log-type Cost Lyu, Ziyuan Wang, Zihao Wu, Hao Yang, Shuai Optimization and Control In [Q. Liao et al., Commun. Math. Sci., 20(2022)], a linear-time Sinkhorn algorithm is developed based on dynamic programming, which significantly reduces the computational complexity involved in solving optimal transport problems. However, this algorithm is specifically designed for the Wasserstein-1 metric. We are curious whether the preceding dynamic programming framework can be extended to tackle optimal transport problems with different transport costs. Notably, two special kinds of optimal transport problems, the Sinkhorn ranking and the far-field reflector and refractor problems, are closely associated with the log-type transport costs. Interestingly, by employing series rearrangement and dynamic programming techniques, it is feasible to perform the matrix-vector multiplication within the Sinkhorn iteration in linear time for this type of cost. This paper provides a detailed exposition of its implementation and applications, with numerical simulations demonstrating the effectiveness and efficiency of our methods. |
| title | A Linear Complexity Algorithm for Optimal Transport Problem with Log-type Cost |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.06578 |