Constructive quantization: approximation by empirical measures
Annales de l'I.H.P. Probabilités et statistiques, Volume 49 (2013) no. 4, p. 1183-1203

In this article, we study the approximation of a probability measure μ on d by its empirical measure μ ^ N interpreted as a random quantization. As error criterion we consider an averaged pth 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.

Dans cet article, nous étudions l’approximation d’une mesure de probabilité μ sur d par sa mesure empirique μ ^ 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.

DOI : https://doi.org/10.1214/12-AIHP489
Classification:  60F25,  65D32
Keywords: constructive quantization, Wasserstein metric, transportation problem, Zador's theorem, Pierce's lemma, random quantization
@article{AIHPB_2013__49_4_1183_0,
     author = {Dereich, Steffen and Scheutzow, Michael and Schottstedt, Reik},
     title = {Constructive quantization: approximation by empirical measures},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {49},
     number = {4},
     year = {2013},
     pages = {1183-1203},
     doi = {10.1214/12-AIHP489},
     zbl = {1283.60063},
     mrnumber = {3127919},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2013__49_4_1183_0}
}
Constructive quantization: approximation by empirical measures. Annales de l'I.H.P. Probabilités et statistiques, Volume 49 (2013) no. 4, pp. 1183-1203. doi : 10.1214/12-AIHP489. http://www.numdam.org/item/AIHPB_2013__49_4_1183_0/

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

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

[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 rth power distortion measures. IEEE Trans. Inform. Theory 28 (1982) 239-247. | MR 651819

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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