Uniqueness and approximate computation of optimal incomplete transportation plans

Álvarez-Esteban, P. C.; del Barrio, E.; Cuesta-Albertos, J. A.; Matrán, C.

Annales de l'I.H.P. Probabilités et statistiques, Tome 47 (2011) no. 2, pp. 358-375.

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.

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.

[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

[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 | Zbl

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

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

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

[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 | Zbl

[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

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

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

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

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

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

[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 | Zbl

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

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

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