Intrinsic Sparsity of Kantorovich solutions

Hosseini, Bamdad; Steinerberger, Stefan

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 $\mu ,\nu$ 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\ne 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/\mathrm{pgcd}(m,n)$ points de Y, et réciproquement, chaque point de Y reçoit de la masse d’au plus $m/\mathrm{pgcd}(m,n)$ points de X.

Let $X,Y$ be two finite sets of points having $\#X=m$ and $\#Y=n$ points with $\mu =(1/m)({\delta }_{x_1}+\cdots +{\delta }_{x_m})$ and $\nu =(1/n)({\delta }_{y_1}+\cdots +{\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\to 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$.

Classification : 49Q20, 90C46

[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