Théorie du contrôle
Intrinsic Sparsity of Kantorovich solutions
[Parcité intrinsèque des solutions de Kantorovich]
Comptes Rendus. Mathématique, Tome 360 (2022) no. G10, pp. 1173-1175.

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 mn, 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 ++δ x m ) and ν=(1/n)(δ y 1 ++δ 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 π:XY. This is impossible when mn. We observe that when mn, 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 :
Accepté le :
Publié le :
DOI : 10.5802/crmath.392
Classification : 49Q20, 90C46
Hosseini, Bamdad 1 ; Steinerberger, Stefan 2

1 Department of Applied Mathematics, University of Washington, Seattle, USA
2 Department of Mathematics, University of Washington, Seattle, USA
@article{CRMATH_2022__360_G10_1173_0,
     author = {Hosseini, Bamdad and Steinerberger, Stefan},
     title = {Intrinsic {Sparsity} of {Kantorovich} solutions},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1173--1175},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {360},
     number = {G10},
     year = {2022},
     doi = {10.5802/crmath.392},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/crmath.392/}
}
TY  - JOUR
AU  - Hosseini, Bamdad
AU  - Steinerberger, Stefan
TI  - Intrinsic Sparsity of Kantorovich solutions
JO  - Comptes Rendus. Mathématique
PY  - 2022
SP  - 1173
EP  - 1175
VL  - 360
IS  - G10
PB  - Académie des sciences, Paris
UR  - http://www.numdam.org/articles/10.5802/crmath.392/
DO  - 10.5802/crmath.392
LA  - en
ID  - CRMATH_2022__360_G10_1173_0
ER  - 
%0 Journal Article
%A Hosseini, Bamdad
%A Steinerberger, Stefan
%T Intrinsic Sparsity of Kantorovich solutions
%J Comptes Rendus. Mathématique
%D 2022
%P 1173-1175
%V 360
%N G10
%I Académie des sciences, Paris
%U http://www.numdam.org/articles/10.5802/crmath.392/
%R 10.5802/crmath.392
%G en
%F CRMATH_2022__360_G10_1173_0
Hosseini, Bamdad; Steinerberger, Stefan. Intrinsic Sparsity of Kantorovich solutions. Comptes Rendus. Mathématique, Tome 360 (2022) no. G10, pp. 1173-1175. doi : 10.5802/crmath.392. http://www.numdam.org/articles/10.5802/crmath.392/

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

[2] Brezis, Haïm 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] König, D. Theorie der endlichen und unendlichen Graphen, Teubner-Archiv zur Mathematik, 6, Teubner, 1936 | Zbl

[4] Mérigot, Quentin; Thibert, Boris 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] von Neumann, John 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] Peyré, Gabriel; Cuturi, Marco 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 :