Quadratically Regularized Optimal Transport: Existence and Multiplicity of Potentials
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913725993189376 |
|---|---|
| author | Nutz, Marcel |
| author_facet | Nutz, Marcel |
| contents | The optimal transport problem with quadratic regularization is useful when sparse couplings are desired. The density of the optimal coupling is described by two functions called potentials; equivalently, potentials can be defined as a solution of the dual problem. We prove the existence of potentials for a general square-integrable cost. Potentials are not necessarily unique, a phenomenon directly related to sparsity of the optimal support. For discrete problems, we describe the family of all potentials based on the connected components of the support, for a graph-theoretic notion of connectedness. On the other hand, we show that continuous problems have unique potentials under standard regularity assumptions, regardless of sparsity. Using potentials, we prove that the optimal support is indeed sparse for small regularization parameter in a continuous setting with quadratic cost, which seems to be the first theoretical guarantee for sparsity in this context. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_06847 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quadratically Regularized Optimal Transport: Existence and Multiplicity of Potentials Nutz, Marcel Optimization and Control Probability 90C25, 49N05 The optimal transport problem with quadratic regularization is useful when sparse couplings are desired. The density of the optimal coupling is described by two functions called potentials; equivalently, potentials can be defined as a solution of the dual problem. We prove the existence of potentials for a general square-integrable cost. Potentials are not necessarily unique, a phenomenon directly related to sparsity of the optimal support. For discrete problems, we describe the family of all potentials based on the connected components of the support, for a graph-theoretic notion of connectedness. On the other hand, we show that continuous problems have unique potentials under standard regularity assumptions, regardless of sparsity. Using potentials, we prove that the optimal support is indeed sparse for small regularization parameter in a continuous setting with quadratic cost, which seems to be the first theoretical guarantee for sparsity in this context. |
| title | Quadratically Regularized Optimal Transport: Existence and Multiplicity of Potentials |
| topic | Optimization and Control Probability 90C25, 49N05 |
| url | https://arxiv.org/abs/2404.06847 |