Universal $L^s$-rate-optimality of $L^r$-optimal quantizers by dilatation and contraction

Sagna, Abass

ESAIM: Probability and Statistics, Tome 13 (2009), pp. 218-246

We investigate in this paper the properties of some dilatations or contractions of a sequence ${\left({\alpha }_n\right)}_{n\ge 1}$ of $L^r$-optimal quantizers of an ${ℝ}^d$-valued random vector $X\in L^r\left(\mathbb{P}\right)$ defined in the probability space $(\Omega ,𝒜,\mathbb{P})$ with distribution ${\mathbb{P}}_X=P$. To be precise, we investigate the $L^s$-quantization rate of sequences ${\alpha }_n^{\theta ,\mu }=\mu +\theta ({\alpha }_n-\mu )=\{\mu +\theta (a-\mu ),a\in {\alpha }_n\}$ when $\theta \in {ℝ}_{+}^{☆},\mu \in ℝ,s\in (0,r)$ or $s\in (r,+\infty )$ and $X\in L^s\left(\mathbb{P}\right)$. We show that for a wide family of distributions, one may always find parameters $(\theta ,\mu )$ such that ${\left({\alpha }_n^{\theta ,\mu }\right)}_{n\ge 1}$ is $L^s$-rate-optimal. For the gaussian and the exponential distributions we show the existence of a couple $({\theta }^{☆},{\mu }^{☆})$ such that ${\left({\alpha }^{{\theta }^{☆},{\mu }^{☆}}\right)}_{n\ge 1}$ also satisfies the so-called $L^s$-empirical measure theorem. Our conjecture, confirmed by numerical experiments, is that such sequences are asymptotically $L^s$-optimal. In both cases the sequence ${\left({\alpha }^{{\theta }^{☆},{\mu }^{☆}}\right)}_{n\ge 1}$ is incredibly close to $L^s$-optimality. However we show (see Rem. 5.4) that this last sequence is not $L^s$-optimal (e.g. when $s$ = 2, $r$ = 1) for the exponential distribution.

Classification : 60G15, 60G35, 41A52
Keywords: rate-optimal quantizers, empirical measure theorem, dilatation, Lloyd algorithm

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

[2] J.C. Fort and G. Pagès, Asymptotics of optimal quantizers for some scalar distributions. J. Comput. Appl. Math. 146 (2002) 253-275. | Zbl | MR

[3] J.H. Friedman, J.L. Bentley and R.A. Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Trans. Math. Software 3 (1977) 209-226. | Zbl

[4] A. Gersho and R. Gray, Vector Quantization and Signal Compression, 6th edition. Kluwer, Boston (1992). | Zbl

[5] S. Graf and H. Luschgy, Foundations of Quantization for Probability Distributions, Lect. Notes Math. 1730. Springer, Berlin (2000). | Zbl | MR

[6] S. Graf, H. Luschgy and G. Pagès, Distorsion mismatch in the quantization of probability measures, ESAIM: PS 12 (2008) 127-153. | MR | Numdam

[7] J. Mcnames, A Fast Nearest-Neighbor algorithm based on a principal axis search tree, IEEE Trans. Pattern Anal. Machine Intelligence 23 (2001) 964-976.

[8] G. Pagès, Space vector quantization method for numerical integration, J. Comput. Appl. Math. 89 (1998) 1-38. | Zbl

[9] G. Pagès, H. Pham and J. Printems, An Optimal markovian quantization algorithm for multidimensional stochastic control problems, Stochastics and Dynamics 4 (2004) 501-545. | Zbl | MR

[10] G. Pagès, H. Pham and J. Printems, Optimal quantization methods and applications to numerical problems in finance, Handbook on Numerical Methods in Finance (S. Rachev, ed.), Birkhauser, Boston (2004) 253-298. | Zbl | MR