Constructive quantization: approximation by empirical measures

Steffen Dereich; Michael Scheutzow; Reik Schottstedt

Annales de l'I.H.P. Probabilités et statistiques (2013)

  • Volume: 49, Issue: 4, page 1183-1203
  • ISSN: 0246-0203

Abstract

top
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 p th moment Wasserstein metric. In the case where 2 p l t ; d , we establish fine upper and lower bounds for the error, ahigh 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.

How to cite

top

Dereich, Steffen, Scheutzow, Michael, and Schottstedt, Reik. "Constructive quantization: approximation by empirical measures." Annales de l'I.H.P. Probabilités et statistiques 49.4 (2013): 1183-1203. <http://eudml.org/doc/271977>.

@article{Dereich2013,
abstract = {In this article, we study the approximation of a probability measure $\mu $ on $\mathbb \{R\}^\{d\}$ by its empirical measure $\hat\{\mu \}_\{N\}$ interpreted as a random quantization. As error criterion we consider an averaged $p$th moment Wasserstein metric. In the case where $2p&lt;d$, we establish fine upper and lower bounds for the error, ahigh 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.},
author = {Dereich, Steffen, Scheutzow, Michael, Schottstedt, Reik},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {constructive quantization; Wasserstein metric; transportation problem; Zador’s theorem; Pierce’s lemma; random quantization; Zador's theorem; Pierce's lemma},
language = {eng},
number = {4},
pages = {1183-1203},
publisher = {Gauthier-Villars},
title = {Constructive quantization: approximation by empirical measures},
url = {http://eudml.org/doc/271977},
volume = {49},
year = {2013},
}

TY - JOUR
AU - Dereich, Steffen
AU - Scheutzow, Michael
AU - Schottstedt, Reik
TI - Constructive quantization: approximation by empirical measures
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2013
PB - Gauthier-Villars
VL - 49
IS - 4
SP - 1183
EP - 1203
AB - In this article, we study the approximation of a probability measure $\mu $ on $\mathbb {R}^{d}$ by its empirical measure $\hat{\mu }_{N}$ interpreted as a random quantization. As error criterion we consider an averaged $p$th moment Wasserstein metric. In the case where $2p&lt;d$, we establish fine upper and lower bounds for the error, ahigh 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.
LA - eng
KW - constructive quantization; Wasserstein metric; transportation problem; Zador’s theorem; Pierce’s lemma; random quantization; Zador's theorem; Pierce's lemma
UR - http://eudml.org/doc/271977
ER -

References

top
  1. [1] M. Ajtai, J. Komlós and G. Tusnàdy. On optimal matchings. Combinatorica 4 (4) (1983) 259–264. Zbl0562.60012MR779885
  2. [2] F. Barthe and C. Bordenave. Combinatorial optimization over two random point sets. Preprint, 2011. Available at arXiv:1103.2734v2. 
  3. [3] J. Beardwood, J. H. Halton and J. M. Hammersley. The shortest path through many points. Proc. Cambridge Philos. Soc.55 (1959) 299–327. Zbl0118.35601MR109316
  4. [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. Zbl1294.60005
  5. [5] J. A. Bucklew and G. L. Wise. Multidimensional asymptotic quantization theory with r th power distortion measures. IEEE Trans. Inform. Theory28 (1982) 239–247. Zbl0476.94013MR651819
  6. [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. Zbl1066.60026MR2158264
  7. [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. Zbl1172.60010MR2562155
  8. [8] S. Dereich and C. Vormoor. The high resolution vector quantization problem with Orlicz norm distortion. J. Theoret. Probab. 24 (2) (2011) 517–544. Zbl1219.94070MR2795051
  9. [9] V. Dobrić and J. E. Yukich. Asymptotics for transportation cost in high dimensions. J. Theoret. Probab. 8 (1) (1995) 97–118. Zbl0811.60022MR1308672
  10. [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. Zbl0782.94001
  11. [11] S. Graf and H. Luschgy. Foundations of Quantization for Probability Distributions. Lecture Notes in Mathematics 1730. Springer, Berlin, 2000. Zbl0951.60003MR1764176
  12. [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. Zbl0819.60031MR1329874
  13. [13] M. Huesmann and T. Sturm. Optimal transport from Lebesgue to Poisson. Preprint, 2010. Available at http://arxiv.org/abs/1012.3845v1. Zbl1279.60024
  14. [14] L. V. Kantorovich. On the translocation of masses. Dokl. Akad. Nauk 37 (7–8) (1942) 227–229. MR9619
  15. [15] L. V. Kantorovich and G. Rubinstein. On a space of completely additive functions. Vestnik Leningrad Univ. Math. 13 (7) (1958) 52–59. Zbl0082.11001MR102006
  16. [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. [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. Zbl1247.65007
  18. [18] G. Pagès. A space quantization method for numerical integration. J. Comput. Appl. Math. 89 (1) (1998) 1–38. Zbl0908.65012MR1625987
  19. [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. Zbl1138.91467MR2083055
  20. [20] G. Pagès and J. Printems. Optimal quadratic quantization for numerics: The Gaussian case. Monte Carlo Methods Appl. 9 (2) (2003) 135–165. Zbl1029.65012MR2006483
  21. [21] G. Pagès and B. Wilbertz. Sharp rate for the dual quantization problem. Preprint, 2010. 
  22. [22] G. Pagès and B. Wilbertz. Optimal Delaunay and Voronoi quantization schemes for pricing American style options. Preprint, 2011. 
  23. [23] S. T. Rachev and L. Rüschendorf. Mass Transportation Problems. Probability and Its Applications I. Springer, New York, 1998. Zbl0990.60500MR1619171
  24. [24] S. T. Rachev and L. Rüschendorf. Mass Transportation Problems. Probability and Its Applications II. Springer, New York, 1998. Zbl0990.60500MR1619171
  25. [25] R. Schottstedt. Constructive quantization by random sampling and numerical applications. Ph.D. thesis, Technical University Berlin, 2012. 
  26. [26] D. W. Stroock and S. R. S. Varadhan. Multidimensional Diffusion Processes. Grundlehren der Mathematischen Wissenschaften 233. Springer, Berlin, 1979. MR532498
  27. [27] M. Talagrand. The transportation cost from the uniform measure to the empirical measure in dimension ≥ 3 . Ann. Probab. 22 (2) (1994) 919–959. Zbl0809.60015MR1288137
  28. [28] C. Villani. Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften 338. Springer, Berlin, 2009. Zbl1156.53003MR2459454
  29. [29] L. N. Wasserstein. Markov processes over denumerable products of spaces describing large systems of automata. Probl. Inf. Transm.5 (1969) 47–52. MR314115
  30. [30] P. L. Zador. Topics in the asymptotic quantization of continuous random variables. Bell Laboratories Technical Memorandum, 1966. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.