General construction and classes of explicit \(L^1\)-optimal couplings. (English) Zbl 1504.49065
Summary: The main scope of this paper is to give some explicit classes of examples of \(L^1\)-optimal couplings. Optimal transportation w.r.t. the Kantorovich metric \(\ell_1\) (resp. the Wasserstein metric \(W_1)\) between two absolutely continuous measures is known since the basic papers of L. V. Kantorovich and G. Sh. Rubinshteĭn [Dokl. Akad. Nauk SSSR 115, 1058–1061 (1957; Zbl 0081.11501)] and V. N. Sudakov [Proc. Steklov Inst. Math. 141, 178 p. (1979; Zbl 0409.60005); translation from Tr. Mat. Inst. Steklov 141, 191 p. (1976)] to occur on rays induced by a decomposition of the basic space (and more generally to higher dimensional decompositions in the case of general measures) induced by the corresponding dual potentials. Several papers have given this kind of structural result and established existence and uniqueness of solutions in varying generality. Since the dual problems pose typically too strong challenges to be solved in explicit form, these structural results have so far been applied for the solution of few particular instances.
First, we give a self-contained review of some basic optimal coupling results and we propose and investigate in particular some basic principles for the construction of \(L^1 \)-optimal couplings given by a reduction principle and some usable forms of the decomposition method. This reduction principle, together with symmetry properties of the reduced measures, gives a hint to the decomposition of the space into sectors and via the non crossing property of optimal transport leads to the choice of transportation rays. The optimality of the induced transports is then a consequence of the characterization results of optimal couplings.
Then, we apply these principles to determine in explicit form \(L^1 \)-optimal couplings for several classes of examples of elliptical distributions. In particular, we give for the first time a general construction of \(L^1 \)-optimal couplings between two bivariate Gaussian distributions. We also discuss optimality of special constructions like shifts and scalings, and provide an extended class of dual functionals allowing for the closed-form computation of the \(\ell_1 \)-metric or of accurate lower bounds of it in a variety of examples.
First, we give a self-contained review of some basic optimal coupling results and we propose and investigate in particular some basic principles for the construction of \(L^1 \)-optimal couplings given by a reduction principle and some usable forms of the decomposition method. This reduction principle, together with symmetry properties of the reduced measures, gives a hint to the decomposition of the space into sectors and via the non crossing property of optimal transport leads to the choice of transportation rays. The optimality of the induced transports is then a consequence of the characterization results of optimal couplings.
Then, we apply these principles to determine in explicit form \(L^1 \)-optimal couplings for several classes of examples of elliptical distributions. In particular, we give for the first time a general construction of \(L^1 \)-optimal couplings between two bivariate Gaussian distributions. We also discuss optimality of special constructions like shifts and scalings, and provide an extended class of dual functionals allowing for the closed-form computation of the \(\ell_1 \)-metric or of accurate lower bounds of it in a variety of examples.
MSC:
| 49Q22 | Optimal transportation |
| 49N15 | Duality theory (optimization) |
| 60E05 | Probability distributions: general theory |
Keywords:
Gaussian distributions; Kantorovich \(\ell_1\)-metric; Kantorovich-Rubinstein theorem; \(L^1\)-Wasserstein distance; Monge-Kantorovich problem; optimal couplings; optimal mass transportationSoftware:
EMDReferences:
| [1] | Alfonsi, A. and Jourdain, B. (2014). A remark on the optimal transport between two probability measures sharing the same copula. Statist. Probab. Lett. 84 131-134. 10.1016/j.spl.2013.09.035 · Zbl 1296.60023 |
| [2] | Ambrosio, L. (2003). Lecture notes on optimal transport problems. In Mathematical Aspects of Evolving Interfaces (Funchal, 2000). Lecture Notes in Math. 1812 1-52. Berlin: Springer. 10.1007/978-3-540-39189-0_1 · Zbl 1047.35001 |
| [3] | Ambrosio, L., Kirchheim, B. and Pratelli, A. (2004). Existence of optimal transport maps for crystalline norms. Duke Math. J. 125 207-241. 10.1215/S0012-7094-04-12521-7 · Zbl 1076.49022 |
| [4] | Ambrosio, L. and Pratelli, A. (2003). Existence and stability results in the \[{L^1}\] theory of optimal transportation. In Optimal Transportation and Applications (Martina Franca, 2001). Lecture Notes in Math. 1813 123-160. Berlin: Springer. 10.1007/978-3-540-44857-0_5 · Zbl 1065.49026 |
| [5] | Bianchini, S. and Daneri, S. (2018). On Sudakov’s type decomposition of transference plans with norm costs. Mem. Amer. Math. Soc. 251 vi+112. 10.1090/memo/1197 · Zbl 1454.49002 |
| [6] | Brenier, Y. (1991). Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math. 44 375-417. 10.1002/cpa.3160440402 · Zbl 0738.46011 |
| [7] | Caffarelli, L.A., Feldman, M. and McCann, R.J. (2002). Constructing optimal maps for Monge’s transport problem as a limit of strictly convex costs. J. Amer. Math. Soc. 15 1-26. 10.1090/S0894-0347-01-00376-9 · Zbl 1053.49032 |
| [8] | Caravenna, L. (2011). A proof of Sudakov theorem with strictly convex norms. Math. Z. 268 371-407. 10.1007/s00209-010-0677-6 · Zbl 1229.49050 |
| [9] | Carlier, G., Oberman, A. and Oudet, E. (2015). Numerical methods for matching for teams and Wasserstein barycenters. ESAIM Math. Model. Numer. Anal. 49 1621-1642. 10.1051/m2an/2015033 · Zbl 1331.49042 |
| [10] | Cuesta-Albertos, J.A., Rüschendorf, L. and Tuero-Díaz, A. (1993). Optimal coupling of multivariate distributions and stochastic processes. J. Multivariate Anal. 46 335-361. 10.1006/jmva.1993.1064 · Zbl 0788.60025 |
| [11] | Dall’Aglio, G. (1956). Sugli estremi dei momenti delle funzioni di ripartizione doppia. Ann. Sc. Norm. Super. Pisa Cl. Sci. (3) 10 35-74. · Zbl 0073.14002 |
| [12] | Dietrich, H. (1988). Zur \(c\)-Konvexität und \(c\)-Subdifferenzierbarkeit von Funktionalen. Optimization 19 355-371. 10.1080/02331938808843352 · Zbl 0649.49011 |
| [13] | Dowson, D.C. and Landau, B.V. (1982). The Fréchet distance between multivariate normal distributions. J. Multivariate Anal. 12 450-455. 10.1016/0047-259X(82)90077-X · Zbl 0501.62038 |
| [14] | Eckstein, S. and Kupper, M. (2021). Computation of optimal transport and related hedging problems via penalization and neural networks. Appl. Math. Optim. 83 639-667. 10.1007/s00245-019-09558-1 · Zbl 1462.49073 |
| [15] | Evans, L.C. and Gangbo, W. (1999). Differential equations methods for the Monge-Kantorovich mass transfer problem. Mem. Amer. Math. Soc. 137 viii+66. 10.1090/memo/0653 · Zbl 0920.49004 |
| [16] | Fang, K.W. (2017). Symmetric Multivariate and Related Distributions. Boca Raton: CRC Press/CRC. |
| [17] | Gangbo, W. and McCann, R.J. (1995). Optimal maps in Monge’s mass transport problem. C. R. Acad. Sci. Paris Sér. I Math. 321 1653-1658. · Zbl 0858.49002 |
| [18] | Gangbo, W. and McCann, R.J. (1996). The geometry of optimal transportation. Acta Math. 177 113-161. 10.1007/BF02392620 · Zbl 0887.49017 |
| [19] | Kantorovic, L.V. and Rubinstein, G.S. (1957). On a functional space and certain extremum problems. Dokl. Akad. Nauk SSSR 115 1058-1061. · Zbl 0081.11501 |
| [20] | Kantorovich, L.V. (1942). On the translocation of masses. C. R. (Dokl.) Acad. Sci. URSS 37 199-201. · Zbl 0061.09705 |
| [21] | Kantorovich, L.V. (1948). On a problem of Monge. Uspekhi Mat. Nauk 3 225-226. In Russian. |
| [22] | Kotz, S. and Nadarajah, S. (2004). Multivariate t Distributions and Their Applications. Cambridge: Cambridge Univ. Press. 10.1017/CBO9780511550683 · Zbl 1100.62059 |
| [23] | Olkin, I. and Pukelsheim, F. (1982). The distance between two random vectors with given dispersion matrices. Linear Algebra Appl. 48 257-263. 10.1016/0024-3795(82)90112-4 · Zbl 0527.60015 |
| [24] | Orlova, D.Y., Zimmerman, N., Meehan, S., Meehan, C., Waters, J. et al. (2016). Earth mover’s distance (EMD): A true metric for comparing biomarker expression levels in cell populations. PLoS ONE 11 e0151859. |
| [25] | Peyré, G. and Cuturi, M. (2018). Computational optimal transport. With applications to data sciences. Found. Trends Mach. Learn. 11 1-262. · Zbl 1475.68011 |
| [26] | Puccetti, G. (2017). An algorithm to approximate the optimal expected inner product of two vectors with given marginals. J. Math. Anal. Appl. 451 132-145. 10.1016/j.jmaa.2017.02.003 · Zbl 1361.65043 |
| [27] | Rachev, S.T. and Rüschendorf, L. (1998). Mass Transportation Problems. Vol. I-II. New York: Springer. · Zbl 0990.60500 |
| [28] | Rubner, Y., Tomasi, C. and Guibas, L.J. (2000). The Earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vis. 40 99-121. · Zbl 1012.68705 |
| [29] | Rüschendorf, L. (1991). Fréchet-bounds and their applications. In Advances in Probability Distributions with Given Marginals (Rome, 1990). Math. Appl. 67 151-187. Dordrecht: Kluwer Academic. · Zbl 0744.60005 |
| [30] | Rüschendorf, L. (1995). Optimal solutions of multivariate coupling problems. Appl. Math. (Warsaw) 23 325-338. 10.4064/am-23-3-325-338 · Zbl 0844.62047 |
| [31] | Rüschendorf, L. (1996). Developments on Fréchet-bounds. In Distributions with Fixed Marginals and Related Topics (Seattle, WA, 1993). Institute of Mathematical Statistics Lecture Notes—Monograph Series 28 273-296. Hayward, CA: IMS. 10.1214/lnms/1215452625 |
| [32] | Rüschendorf, L. (1998). Wasserstein metric. In Encyclopaedia of Mathematics. Supplement, I, II, III (M. Hazewinkel, ed.) Kluwer Academic (1997-2001). |
| [33] | Rüschendorf, L. and Rachev, S.T. (1990). A characterization of random variables with minimum \[{L^2}\]-distance. J. Multivariate Anal. 32 48-54. 10.1016/0047-259X(90)90070-X · Zbl 0688.62034 |
| [34] | Ruttenberg, B.E. and Singh, A.K. (2011). Indexing the Earth mover’s distance using normal distributions. Proc. VLDB Endow. 5 205-216. |
| [35] | Sudakov, V.N. (1979). Geometric problems in the theory of infinite-dimensional probability distributions. Proc. Steklov Inst. Math. (translation from Tr. Mat. Inst. Steklov 141 (1976)) 141 1-178. · Zbl 0409.60005 |
| [36] | Trudinger, N.S. and Wang, X.-J. (2001). On the Monge mass transfer problem. Calc. Var. Partial Differential Equations 13 19-31. 10.1007/PL00009922 · Zbl 1010.49030 |
| [37] | Uckelmann, L. (1998). Über das Monge-Kantorovich Transportproblem und dessen Verallgemeinerungen Dissertation, Univ. Freiburg. · Zbl 0917.90117 |
| [38] | Villani, C. (2009). Optimal Transport. Old and New. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 338. Berlin: Springer. 10 · Zbl 1156.53003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
