Intrinsic Sparsity of Kantorovich solutions
Let $X,Y$ be two finite sets of points having $\#X = m$ and $\#Y = n$ points with $\mu = (1/m)(\delta _{x_1} + \dots + \delta _{x_m})$ and $\nu = (1/n) (\delta _{y_1} + \dots + \delta _{y_n})$ being the associated uniform probability measures. A result of Birkhoff implies that if $m = n$, then the K...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Académie des sciences
2022-10-01
|
| Series: | Comptes Rendus. Mathématique |
| Online Access: | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.392/ |
| _version_ | 1797651493394841600 |
|---|---|
| author | Hosseini, Bamdad Steinerberger, Stefan |
| author_facet | Hosseini, Bamdad Steinerberger, Stefan |
| author_sort | Hosseini, Bamdad |
| collection | DOAJ |
| description | Let $X,Y$ be two finite sets of points having $\#X = m$ and $\#Y = n$ points with $\mu = (1/m)(\delta _{x_1} + \dots + \delta _{x_m})$ and $\nu = (1/n) (\delta _{y_1} + \dots + \delta _{y_n})$ being the associated uniform probability measures. A result of Birkhoff implies that if $m = n$, then the Kantorovich problem has a solution which also solves the Monge problem: optimal transport can be realized with a bijection $\pi : X \rightarrow Y$. This is impossible when $m \ne n$. We observe that when $m \ne n$, there exists a solution of the Kantorovich problem such that the mass of each point in $X$ is moved to at most $n/\gcd (m,n)$ different points in $Y$ and that, conversely, each point in $Y$ receives mass from at most $m/\gcd (m,n)$ points in $X$. |
| first_indexed | 2024-03-11T16:16:36Z |
| format | Article |
| id | doaj.art-c14be17ae52d4040b7635049f30b1d4d |
| institution | Directory Open Access Journal |
| issn | 1778-3569 |
| language | English |
| last_indexed | 2024-03-11T16:16:36Z |
| publishDate | 2022-10-01 |
| publisher | Académie des sciences |
| record_format | Article |
| series | Comptes Rendus. Mathématique |
| spelling | doaj.art-c14be17ae52d4040b7635049f30b1d4d2023-10-24T14:20:27ZengAcadémie des sciencesComptes Rendus. Mathématique1778-35692022-10-01360G101173117510.5802/crmath.39210.5802/crmath.392Intrinsic Sparsity of Kantorovich solutionsHosseini, Bamdad0Steinerberger, Stefan1Department of Applied Mathematics, University of Washington, Seattle, USADepartment of Mathematics, University of Washington, Seattle, USALet $X,Y$ be two finite sets of points having $\#X = m$ and $\#Y = n$ points with $\mu = (1/m)(\delta _{x_1} + \dots + \delta _{x_m})$ and $\nu = (1/n) (\delta _{y_1} + \dots + \delta _{y_n})$ being the associated uniform probability measures. A result of Birkhoff implies that if $m = n$, then the Kantorovich problem has a solution which also solves the Monge problem: optimal transport can be realized with a bijection $\pi : X \rightarrow Y$. This is impossible when $m \ne n$. We observe that when $m \ne n$, there exists a solution of the Kantorovich problem such that the mass of each point in $X$ is moved to at most $n/\gcd (m,n)$ different points in $Y$ and that, conversely, each point in $Y$ receives mass from at most $m/\gcd (m,n)$ points in $X$.https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.392/ |
| spellingShingle | Hosseini, Bamdad Steinerberger, Stefan Intrinsic Sparsity of Kantorovich solutions Comptes Rendus. Mathématique |
| title | Intrinsic Sparsity of Kantorovich solutions |
| title_full | Intrinsic Sparsity of Kantorovich solutions |
| title_fullStr | Intrinsic Sparsity of Kantorovich solutions |
| title_full_unstemmed | Intrinsic Sparsity of Kantorovich solutions |
| title_short | Intrinsic Sparsity of Kantorovich solutions |
| title_sort | intrinsic sparsity of kantorovich solutions |
| url | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.392/ |
| work_keys_str_mv | AT hosseinibamdad intrinsicsparsityofkantorovichsolutions AT steinerbergerstefan intrinsicsparsityofkantorovichsolutions |