Uniqueness and approximate computation of optimal incomplete transportation plans
Annales de l'I.H.P. Probabilités et statistiques, Volume 47 (2011) no. 2, p. 358-375

For α∈(0, 1) an α-trimming, P∗, of a probability P is a new probability obtained by re-weighting the probability of any Borel set, B, according to a positive weight function, f≤1/(1-α), in the way P∗(B)=Bf(x)P(dx). If P, Q are probability measures on euclidean space, we consider the problem of obtaining the best L2-Wasserstein approximation between: (a) a fixed probability and trimmed versions of the other; (b) trimmed versions of both probabilities. These best trimmed approximations naturally lead to a new formulation of the mass transportation problem, where a part of the mass need not be transported. We explore the connections between this problem and the similarity of probability measures. As a remarkable result we obtain the uniqueness of the optimal solutions. These optimal incomplete transportation plans are not easily computable, but we provide theoretical support for Monte-Carlo approximations. Finally, we give a CLT for empirical versions of the trimmed distances and discuss some statistical applications.

Pour α∈(0, 1), une α-coupe P∗ d'une probabilité P selon une fonction positive f majorée par 1/(1-α) est la probabilité obtenue pour tout ensemble de Borel B par P∗(B)=Bf(x)P(dx). Si P, Q sont deux probabilités sur l'espace euclidien, on considère le problème de minimiser la distance de Wasserstein L2 entre (a) une probabilité et ses versions coupées (b) les versions coupées de deux probabilités. Ce problème mène naturellement à une nouvelle formulation du problème de transport de masse, où une partie de la masse ne doit pas être transportée. Nous explorons les liaisons entre ce problème et la similitude des mesures de probabilité. Un de nos résultats remarquables est l'unicité du transport de masse. Ces plans de transport optimal incomplets ne sont pas facilement calculables mais nous fournissons un appui théorique pour des approximations de Monte-Carlo. Enfin, nous donnons un TCL pour les versions empiriques des distances coupées et discutons certaines applications statistiques.

DOI : https://doi.org/10.1214/09-AIHP354
Classification:  49Q20,  60A10,  60B10,  28A50
Keywords: incomplete mass transportation problem, multivariate distributions, optimal transportation plan, similarity, trimming, uniqueness, trimmed probability, clt
@article{AIHPB_2011__47_2_358_0,
     author = {\'Alvarez-Esteban, P. C. and del Barrio, E. and Cuesta-Albertos, J. A. and Matr\'an, C.},
     title = {Uniqueness and approximate computation of optimal incomplete transportation plans},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {47},
     number = {2},
     year = {2011},
     pages = {358-375},
     doi = {10.1214/09-AIHP354},
     zbl = {1215.49042},
     mrnumber = {2814414},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2011__47_2_358_0}
}
Álvarez-Esteban, P. C.; del Barrio, E.; Cuesta-Albertos, J. A.; Matrán, C. Uniqueness and approximate computation of optimal incomplete transportation plans. Annales de l'I.H.P. Probabilités et statistiques, Volume 47 (2011) no. 2, pp. 358-375. doi : 10.1214/09-AIHP354. http://www.numdam.org/item/AIHPB_2011__47_2_358_0/

[1] P. C. Álvarez-Esteban, E. Del Barrio, J. A. Cuesta-Albertos and C. Matrán. Trimmed comparison of distributions. J. Amer. Statist. Assoc. 103 (2008) 697-704. | MR 2435470 | Zbl pre05564523

[2] L. Ambrosio. Lecture Notes on Optimal Transport Problems, Mathematical Aspects of Evolving Interfaces. Lecture Notes in Math. 1812. Springer, Berlin/New York, 2003. | MR 2011032 | Zbl 1047.35001

[3] P. J. Bickel and D. A. Freedman. Some asymptotic theory for the bootstrap. Ann. Statist. 9 (1981) 1196-1217. | MR 630103 | Zbl 0449.62034

[4] Y. Brenier. Polar decomposition and increasing rearrangement of vector fields. C. R. Acad. Sci. Paris Ser. I Math. 305 (1987) 805-808. | MR 923203 | Zbl 0652.26017

[5] Y. Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math. 44 (1991) 375-417. | MR 1100809 | Zbl 0738.46011

[6] L. A. Caffarelli, M. Feldman and R. J. Mccann. Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs. J. Amer. Math. Soc. 15 (2002) 1-26. | MR 1862796 | Zbl 1053.49032

[7] L. A. Caffarelli and R. J. Mccann. Free boundaries in optimal transport and Monge-Ampére obstacle problems. Ann. of Math. (2006), to appear. | Zbl 1196.35231

[8] I. J. Cascos and M. López-Díaz. Integral trimmed regions. J. Multivariate Anal. 96 (2005) 404-424. | MR 2204986 | Zbl 1122.62037

[9] I. J. Cascos and M. López-Díaz. Consistency of the α-trimming of a probability. Applications to central regions. Bernoulli 14 (2008) 580-592. | MR 2544103 | Zbl 1158.60338

[10] M. Csörgő and L. Horváth. Weighted Approximations in Probability and Statistics. Wiley, New York, 1993. | MR 1215046 | Zbl 0770.60038

[11] J. A. Cuesta-Albertos and C. Matrán. Notes on the Wasserstein metric in Hilbert spaces. Ann. Probab. 17 (1989) 1264-1276. | MR 1009457 | Zbl 0688.60011

[12] J. A. Cuesta-Albertos, C. Matrán and A. J. Tuero. Optimal transportation plans and convergence in distribution. J. Multivariate Anal. 60 (1997) 72-83. | MR 1441460 | Zbl 0894.60012

[13] J. A. Cuesta-Albertos, C. Matrán and A. J. Tuero. On the monotonicity of optimal transportation plans. J. Math. Anal. Appl. 215 (1997) 86-94. | MR 1478852 | Zbl 0892.60020

[14] L. C. Evans and R. F. Gariepy. Measure Theory and Fine Properties of Functions. Studies in Advanced Mathematics. CRC Press, Boca Raton, FL, 1992. | MR 1158660 | Zbl 0804.28001

[15] M. Feldman and R. J. Mccann. Uniqueness and transport density in Monge's mass transportation problem. Calc. Var. 15 (2002) 81-113. | MR 1920716 | Zbl 1003.49031

[16] A. J. Figalli. The optimal partial transport problem. Arch. Rational Mech. Anal. 195 (2010), 533-560. | MR 2592287 | Zbl pre05675030

[17] W. Gangbo and R. J. Mccann. Shape recognition via Wasserstein distance. Quart. Appl. Math. 58 (2000) 705-737. | MR 1788425 | Zbl 1039.49038

[18] A. Gordaliza. Best approximations to random variables based on trimming procedures. J. Approx. Theory 64 (1991) 162-180. | MR 1091467 | Zbl 0745.41030

[19] R. J. Mccann. Existence and uniqueness of monotone measure-preserving maps. Duke Math. J. 80 (1995) 309-323. | MR 1369395 | Zbl 0873.28009

[20] S. T. Rachev and L. Rüschendorf. Mass Transportation Problems 2. Springer, New York, 1998. | Zbl 0990.60500

[21] L. Rüschendorf and S. T. Rachev. A characterization of random variables with minimum L2-distance. J. Multivariate Anal. 32 (1990) 48-54. | MR 1035606 | Zbl 0688.62034

[22] A. Tuero. On the stochastic convergence of representations based on Wasserstein metrics. Ann. Probab. 21 (1993) 72-85. | MR 1207216 | Zbl 0770.60012

[23] A. W. Van Der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes. Springer, New York, 1996. | MR 1385671 | Zbl 0862.60002

[24] C. Villani. Topics in Optimal Transportation. Graduate Studies in Mathematics 58. Amer. Math. Soc., Providence, RI, 2003. | MR 1964483 | Zbl 1106.90001