Rates of convergence for the empirical quantization error. (English) Zbl 1018.60032

Let \(X_1,X_2,\dots\) be \(d\)-dimensional i.i.d random variables with distribution \(P\), and let \(P_k\) denote the empirical measure of \(X_1,\dots,X_k\). The authors provide rates of convergence for the a.s. limiting behaviour of the empirical quantization error, i.e. they prove a.s. bounds, as \(k\to\infty \), for \[ Y_{k,r}(P)=\sup_{n\geq 1}|e_{n,r}(P_k)^r - e_{n,r}(P)^r|\quad\text{ and }\quad Z_{k,r}(P)=\sup|e_{n,r}(P_k) -e_{n,r}(P)|, \] respectively. Here \[ e_{n,r}(P)=\inf\{(E_P\|X-f(X)\|^r)^{1/r}\}\quad \text{ and }\quad e_{n,r}(P_k)=\inf\Bigl\{\Bigl (\frac 1k\sum^k_{i=1}\|X_i-f(X_i)\|^r\Bigr)^{1/r}\Bigr\} \] where the infimum is taken over all measurable maps \(f\) with at most \(n\) values in \(\mathbb{R}^d\), and where \(\|\cdot \|\) denotes any norm in \(\mathbb{R}^d\).


60F15 Strong limit theorems
60E15 Inequalities; stochastic orderings
62H30 Classification and discrimination; cluster analysis (statistical aspects)
94A29 Source coding
Full Text: DOI


[1] ALEXANDER, K. (1984). Probability inequalities for empirical processes and a law of the iterated logarithm. Ann. Probab. 12 1041-1067. [Correction (1987). Ann. Probab. 15 428-430.] · Zbl 0549.60024
[2] BALLY, V. and PAGÈS, G. (2000). A quantization algorithm for solving multidimensional optimal stopping problems. Technical report, Univ. Paris 6.
[3] GERSHO, A. and GRAY, R. M. (1992). Vector Quantization and Signal Compression. Kluwer, Boston. · Zbl 0782.94001
[4] GRAF, S. and LUSCHGY, H. (2000). Foundations of Quantization for Probability Distributions. Lecture Notes in Math. 1730. Springer, Berlin. · Zbl 0951.60003
[5] GRAF, S. and LUSCHGY, H. (2001). The quantization dimension of self-similar distributions. Math. Nachrichten. · Zbl 1029.28003
[6] HOCHBAUM, D. and STEELE, J. M. (1982). Steinhaus’s geometric location problem for random samples in the plane. Adv. Appl. Probab. 14 56-67. JSTOR: · Zbl 0501.60040
[7] HOEFFDING, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13-30. JSTOR: · Zbl 0127.10602
[8] PAGÈS, G. (1997). A space vector quantization method for numerical integration. J. Comput. Appl. Math. 89 1-38. · Zbl 0908.65012
[9] RACHEV, S. T. and RÜSCHENDORF, L. (1998). Mass Transportation Problems I, II. Springer, New York. · Zbl 0990.60500
[10] RHEE, W. T. and TALAGRAND, M. (1989). A concentration inequality for the k-median problem. Math. Oper. Res. 14 189-202. JSTOR: · Zbl 0682.90036
[11] TALGRAND, M. (1994). The transportation cost from the uniform measure to the empirical measure in dimension 3. Ann. Probab. 22 919-959. · Zbl 0809.60015
[12] WONG, M. A. (1984). Asymptotic properties of univariate sample k-means clusters. J. Classification 1 255-270. · Zbl 0572.62053
[13] ZEMEL, E. (1985). Probabilistic analysis of geometric location problems. SIAM. J. Algebraic Discrete Methods 6 189-200. · Zbl 0569.90022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.