Constructive quantization: approximation by empirical measures

Dereich, Steffen; Scheutzow, Michael; Schottstedt, Reik

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

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.

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.

Classification: 60F25, 65D32
Keywords: 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.