Solving Semi-Discrete Optimal Transport Problems: star shapedeness and Newton's method
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915561748824064 |
|---|---|
| author | Dieci, Luca Omarov, Daniyar |
| author_facet | Dieci, Luca Omarov, Daniyar |
| contents | In this work, we propose a novel implementation of Newton's method for solving semi-discrete optimal transport (OT) problems for cost functions which are a positive combination of $p$-norms, $1<p<\infty$. It is well understood that the solution of a semi-discrete OT problem is equivalent to finding a partition of a bounded region in Laguerre cells, and we prove that the Laguerre cells are star-shaped with respect to the target points. By exploiting the geometry of the Laguerre cells, we obtain an efficient and reliable implementation of Newton's method to find the sought network structure. We provide implementation details and extensive results in support of our technique in 2-d problems, as well as comparison with other approaches used in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_07489 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Solving Semi-Discrete Optimal Transport Problems: star shapedeness and Newton's method Dieci, Luca Omarov, Daniyar Numerical Analysis Optimization and Control 65D99, 65K99, 49M15 In this work, we propose a novel implementation of Newton's method for solving semi-discrete optimal transport (OT) problems for cost functions which are a positive combination of $p$-norms, $1<p<\infty$. It is well understood that the solution of a semi-discrete OT problem is equivalent to finding a partition of a bounded region in Laguerre cells, and we prove that the Laguerre cells are star-shaped with respect to the target points. By exploiting the geometry of the Laguerre cells, we obtain an efficient and reliable implementation of Newton's method to find the sought network structure. We provide implementation details and extensive results in support of our technique in 2-d problems, as well as comparison with other approaches used in the literature. |
| title | Solving Semi-Discrete Optimal Transport Problems: star shapedeness and Newton's method |
| topic | Numerical Analysis Optimization and Control 65D99, 65K99, 49M15 |
| url | https://arxiv.org/abs/2310.07489 |