Intrinsic Sparsity of Kantorovich solutions

Bamdad Hosseini; Stefan Steinerberger

doi:10.5802/crmath.392

Théorie du contrôle

Intrinsic Sparsity of Kantorovich solutions
[Parcité intrinsèque des solutions de Kantorovich]

Bamdad Hosseini ¹ ; Stefan Steinerberger ²

¹ Department of Applied Mathematics, University of Washington, Seattle, USA
² Department of Mathematics, University of Washington, Seattle, USA

Comptes Rendus. Mathématique, Volume 360 (2022), pp. 1173-1175.

Résumé
Abstract

Soient $X$ et $Y$ deux ensembles de points de cardinaux respectifs $m$ et $n$ ; et $μ, ν$ les mesures de probabilité associées. Quand $m = n$ , un résultat de Birkhoff assure que le problème de Kantorovitch a une solution qui résout aussi le problème de Monge : une bijection réalise le transport optimal. Quand $m \neq n$ , nous montrons que le problème de Kantorovitch admet une solution telle que chaque point de X se déplace vers au plus $n / pgcd (m, n)$ points de Y, et réciproquement, chaque point de Y reçoit de la masse d’au plus $m / pgcd (m, n)$ points de X.

Let $X, Y$ be two finite sets of points having $# X = m$ and $# Y = n$ points with $μ = (1 / m) (δ_{x_{1}} + \dots + δ_{x_{m}})$ and $ν = (1 / n) (δ_{y_{1}} + \dots + δ_{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 $π : X \to Y$ . This is impossible when $m \neq n$ . We observe that when $m \neq 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$ .

Reçu le : 2022-06-03
Accepté le : 2022-06-05
Publié le : 2022-10-04

DOI : 10.5802/crmath.392

Classification : 49Q20, 90C46

Affiliations des auteurs :

Bamdad Hosseini ¹ ; Stefan Steinerberger ²

¹ Department of Applied Mathematics, University of Washington, Seattle, USA
² Department of Mathematics, University of Washington, Seattle, USA

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2022__360_G10_1173_0,
     author = {Bamdad Hosseini and Stefan Steinerberger},
     title = {Intrinsic {Sparsity} of {Kantorovich} solutions},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1173--1175},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {360},
     year = {2022},
     doi = {10.5802/crmath.392},
     language = {en},
}

TY  - JOUR
AU  - Bamdad Hosseini
AU  - Stefan Steinerberger
TI  - Intrinsic Sparsity of Kantorovich solutions
JO  - Comptes Rendus. Mathématique
PY  - 2022
SP  - 1173
EP  - 1175
VL  - 360
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.392
LA  - en
ID  - CRMATH_2022__360_G10_1173_0
ER  -

%0 Journal Article
%A Bamdad Hosseini
%A Stefan Steinerberger
%T Intrinsic Sparsity of Kantorovich solutions
%J Comptes Rendus. Mathématique
%D 2022
%P 1173-1175
%V 360
%I Académie des sciences, Paris
%R 10.5802/crmath.392
%G en
%F CRMATH_2022__360_G10_1173_0

Bamdad Hosseini; Stefan Steinerberger. Intrinsic Sparsity of Kantorovich solutions. Comptes Rendus. Mathématique, Volume 360 (2022), pp. 1173-1175. doi : 10.5802/crmath.392. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.392/

Bibliographie
Cité par

[1] Garett Birkhoff Tres observaciones sobre el algebra lineal, Rev., Ser. A, Univ. Nac. Tucumán, Volume 5 (1946), pp. 147-151 | Zbl

[2] Haïm Brezis Remarks on the Monge-Kantorovich problem in the discrete setting, C. R. Math. Acad. Sci. Paris, Volume 356 (2018) no. 2, pp. 207-213 | DOI | MR | Zbl

[3] D. König Theorie der endlichen und unendlichen Graphen, Teubner-Archiv zur Mathematik, 6, Teubner, 1936 | Zbl

[4] Quentin Mérigot; Boris Thibert Optimal transport: discretization and algorithms, Geometric partial differential equations. Part 2 (Handbook of Numerical Analysis), Volume 22, Elsevier, 2021, pp. 133-212 | DOI | MR | Zbl

[5] John von Neumann A certain zero-sum two-person game equivalent to an optimal assignment problem, Contributions to the theory of games. Vol. 2 (Annals of Mathematics Studies), Volume 28, Princeton University Press, 1953, pp. 5-12 | MR | Zbl

[6] Gabriel Peyré; Marco Cuturi Computational optimal transport: With applications to data science, Found. Trends Mach. Learn., Volume 11 (2018) no. 5-6, pp. 355-407 | DOI | Zbl

Cité par Sources :

Commentaires - Politique