Unbalanced Optimal Transport and Maximum Mean Discrepancies: Interconnections and Rapid Evaluation
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_ | 1866911876250599424 |
|---|---|
| author | Lakshmanan, Rajmadan Pichler, Alois |
| author_facet | Lakshmanan, Rajmadan Pichler, Alois |
| contents | This contribution presents substantial computational advancements to compare measures even with varying masses. Specifically, we utilize the nonequispaced fast Fourier transform to accelerate the radial kernel convolution in unbalanced optimal transport approximation, built upon the Sinkhorn algorithm. We also present accelerated schemes for maximum mean discrepancies involving kernels. Our approaches reduce the arithmetic operations needed to compute distances from $\mathcal O(n^2)$ to $\mathcal O(n\log n)$, opening the door to handle large and high-dimensional datasets efficiently. Furthermore, we establish robust connections between transportation problems, encompassing Wasserstein distance and unbalanced optimal transport, and maximum mean discrepancies. This empowers practitioners with compelling rationale to opt for adaptable distances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_13618 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Unbalanced Optimal Transport and Maximum Mean Discrepancies: Interconnections and Rapid Evaluation Lakshmanan, Rajmadan Pichler, Alois Optimization and Control 90C08, 90C15, 60G07 This contribution presents substantial computational advancements to compare measures even with varying masses. Specifically, we utilize the nonequispaced fast Fourier transform to accelerate the radial kernel convolution in unbalanced optimal transport approximation, built upon the Sinkhorn algorithm. We also present accelerated schemes for maximum mean discrepancies involving kernels. Our approaches reduce the arithmetic operations needed to compute distances from $\mathcal O(n^2)$ to $\mathcal O(n\log n)$, opening the door to handle large and high-dimensional datasets efficiently. Furthermore, we establish robust connections between transportation problems, encompassing Wasserstein distance and unbalanced optimal transport, and maximum mean discrepancies. This empowers practitioners with compelling rationale to opt for adaptable distances. |
| title | Unbalanced Optimal Transport and Maximum Mean Discrepancies: Interconnections and Rapid Evaluation |
| topic | Optimization and Control 90C08, 90C15, 60G07 |
| url | https://arxiv.org/abs/2306.13618 |