Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-22T19:01:13.062Z Has data issue: false hasContentIssue false

Universal Ls -rate-optimality of Lr -optimal quantizersby dilatation and contraction

Published online by Cambridge University Press:  12 June 2009

Abass Sagna*
Affiliation:
Laboratoire de Probabilités et Modèles Aléatoires, UMR 7599, Université Pierre et Marie Curie, Case 188, 4 place Jussieu, 75252 Cedex 05, Paris, France; [email protected]
Get access

Abstract

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

Type
Research Article
Copyright
© EDP Sciences, SMAI, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Delattre, S., Graf, S., Luschgy, H. and Pagès, G., Quantization of probability distributions under norm-based distribution measures. Statist. Decisions 22 (2004) 261282. CrossRef
Fort, J.C. and Pagès, G., Asymptotics of optimal quantizers for some scalar distributions. J. Comput. Appl. Math. 146 (2002) 253275. CrossRef
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.
A. Gersho and R. Gray, Vector Quantization and Signal Compression, 6th edition. Kluwer, Boston (1992).
S. Graf and H. Luschgy, Foundations of Quantization for Probability Distributions, Lect. Notes Math. 1730. Springer, Berlin (2000).
S. Graf, H. Luschgy and G. Pagès, Distorsion mismatch in the quantization of probability measures, ESAIM: PS 12 (2008) 127–153.
J. McNames, A Fast Nearest-Neighbor algorithm based on a principal axis search tree, IEEE Trans. Pattern Anal. Machine Intelligence 23 (2001) 964–976.
G. Pagès, Space vector quantization method for numerical integration, J. Comput. Appl. Math. 89 (1998) 1–38.
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.
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.