Constructive quantization: approximation by empirical measures

Dereich, Steffen; Scheutzow, Michael; Schottstedt, Reik

Annales de l'I.H.P. Probabilités et statistiques, Tome 49 (2013) no. 4, pp. 1183-1203.

Dans cet article, nous étudions l’approximation d’une mesure de probabilité $\mu$ sur ${ℝ}^d$ par sa mesure empirique ${\widehat{\mu }}_N$, interprétée comme quantification aléatoire. Comme critère d’erreur, nous considérons une moyenne de métrique de Wasserstein d’ordre $p$. Dans le cas $2p<d$, nous établissons des bornes supérieures et inférieures améliorées pour l’erreur, une formule haute résolution. De plus, nous donnons une estimation universelle à base de moments, nomméee estimation du type Pierce. En particulier, nous prouvons que, sous de faibles hypothèses, la quantification par des mesures empiriques est d'ordre optimal.

In this article, we study the approximation of a probability measure $\mu$ on ${ℝ}^d$ by its empirical measure ${\widehat{\mu }}_N$ interpreted as a random quantization. As error criterion we consider an averaged $p$th moment Wasserstein metric. In the case where $2p<d$, we establish fine upper and lower bounds for the error, a high resolution formula. Moreover, we provide a universal estimate based on moments, a Pierce type estimate. In particular, we show that quantization by empirical measures is of optimal order under weak assumptions.

Classification : 60F25, 65D32
Mots clés : constructive quantization, Wasserstein metric, transportation problem, Zador's theorem, Pierce's lemma, random quantization

[1] M. Ajtai, J. Komlós and G. Tusnàdy. On optimal matchings. Combinatorica 4 (4) (1983) 259-264. | MR

[2] F. Barthe and C. Bordenave. Combinatorial optimization over two random point sets. Preprint, 2011. Available at arXiv:1103.2734v2.

[3] J. Beardwood, J. H. Halton and J. M. Hammersley. The shortest path through many points. Proc. Cambridge Philos. Soc. 55 (1959) 299-327. | MR

[4] E. Boissard and T. Le Gouic. On the mean speed of convergence of empirical and occupation measures in Wasserstein distance. Preprint, 2011. Available at arXiv:1105.5263v1.

[5] J. A. Bucklew and G. L. Wise. Multidimensional asymptotic quantization theory with $r$th power distortion measures. IEEE Trans. Inform. Theory 28 (1982) 239-247. | MR

[6] S. Delattre, S. Graf, H. Luschgy and G. Pagès. Quantization of probability distributions under norm-based distortion measures. Statist. Decisions 22 (4) (2004) 261-282. | MR

[7] S. Dereich. Asymptotic formulae for coding problems and intermediate optimization problems: A review. In Trends in Stochastic Analysis 187-232. Cambridge Univ. Press, Cambridge, 2009. | MR

[8] S. Dereich and C. Vormoor. The high resolution vector quantization problem with Orlicz norm distortion. J. Theoret. Probab. 24 (2) (2011) 517-544. | MR

[9] V. Dobrić and J. E. Yukich. Asymptotics for transportation cost in high dimensions. J. Theoret. Probab. 8 (1) (1995) 97-118. | MR

[10] A. Gersho and R. M. Gray. Vector Quantization and Signal Processing. The Springer International Series in Engineering and Computer Science 1. Springer, New York, 1992.

[11] S. Graf and H. Luschgy. Foundations of Quantization for Probability Distributions. Lecture Notes in Mathematics 1730. Springer, Berlin, 2000. | MR

[12] J. Horowitz and R. L. Karandikar. Mean rates of convergence of empirical measures in the Wasserstein metric. J. Comput. Appl. Math. 55 (3) (1994) 261-273. | MR

[13] M. Huesmann and T. Sturm. Optimal transport from Lebesgue to Poisson. Preprint, 2010. Available at http://arxiv.org/abs/1012.3845v1.

[14] L. V. Kantorovich. On the translocation of masses. Dokl. Akad. Nauk 37 (7-8) (1942) 227-229. | MR

[15] L. V. Kantorovich and G. Rubinstein. On a space of completely additive functions. Vestnik Leningrad Univ. Math. 13 (7) (1958) 52-59. | MR

[16] G. Monge. Mémoire sur la théorie des déblais et des remblais. Mémoires de l'Académie Royale des Sciences XVIII-XIX (1781) 666-704.

[17] T. Müller-Gronbach, K. Ritter and L. Yaroslavtseva. A derandomization of the Euler scheme for scalar stochastic differential equations. Preprint 80, DFG Priority Program 1324, 2011. Available at http://www.dfg-spp1324.de/publications.php?lang=en.

[18] G. Pagès. A space quantization method for numerical integration. J. Comput. Appl. Math. 89 (1) (1998) 1-38. | MR

[19] G. Pagès, H. Pham and J. Printems. Optimal quantization methods and applications to numerical problems in finance. In Handbook on Numerical Methods in Finance 253-298. Birkhäuser, Boston, 2004. | MR

[20] G. Pagès and J. Printems. Optimal quadratic quantization for numerics: The Gaussian case. Monte Carlo Methods Appl. 9 (2) (2003) 135-165. | MR

[21] G. Pagès and B. Wilbertz. Sharp rate for the dual quantization problem. Preprint, 2010.

[22] G. Pagès and B. Wilbertz. Optimal Delaunay and Voronoi quantization schemes for pricing American style options. Preprint, 2011.

[23] S. T. Rachev and L. Rüschendorf. Mass Transportation Problems. Probability and Its Applications I. Springer, New York, 1998. | MR

[24] S. T. Rachev and L. Rüschendorf. Mass Transportation Problems. Probability and Its Applications II. Springer, New York, 1998. | MR

[25] R. Schottstedt. Constructive quantization by random sampling and numerical applications. Ph.D. thesis, Technical University Berlin, 2012.

[26] D. W. Stroock and S. R. S. Varadhan. Multidimensional Diffusion Processes. Grundlehren der Mathematischen Wissenschaften 233. Springer, Berlin, 1979. | MR

[27] M. Talagrand. The transportation cost from the uniform measure to the empirical measure in dimension $\ge 3$. Ann. Probab. 22 (2) (1994) 919-959. | MR

[28] C. Villani. Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften 338. Springer, Berlin, 2009. | MR

[29] L. N. Wasserstein. Markov processes over denumerable products of spaces describing large systems of automata. Probl. Inf. Transm. 5 (1969) 47-52. | MR

[30] P. L. Zador. Topics in the asymptotic quantization of continuous random variables. Bell Laboratories Technical Memorandum, 1966.