Universal Ls-rate-optimality of Lr-optimal quantizers by dilatation and contraction

Abass Sagna

ESAIM: Probability and Statistics (2009)

  • Volume: 13, page 218-246
  • ISSN: 1292-8100

Abstract

top
We investigate in this paper the properties of some dilatations or contractions of a sequence (αn)n≥1 of Lr-optimal quantizers of an d -valued random vector X L r ( ) defined in the probability space ( Ω , 𝒜 , ) with distribution X = P . To be precise, we investigate the Ls-quantization rate of sequences α n θ , μ = μ + θ ( α n - μ ) = { μ + θ ( a - μ ) , a α n } when θ + , μ , s ( 0 , r ) or s ∈ (r, +∞) and X L s ( ) . 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.

How to cite

top

Sagna, Abass. "Universal Ls-rate-optimality of Lr-optimal quantizers by dilatation and contraction." ESAIM: Probability and Statistics 13 (2009): 218-246. <http://eudml.org/doc/250635>.

@article{Sagna2009,
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. },
author = {Sagna, Abass},
journal = {ESAIM: Probability and Statistics},
keywords = {Rate-optimal quantizers; empirical measure theorem; dilatation; Lloyd algorithm; rate-optimal quantizers; Gaussian distribution; Lloyd's algorithm},
language = {eng},
month = {6},
pages = {218-246},
publisher = {EDP Sciences},
title = {Universal Ls-rate-optimality of Lr-optimal quantizers by dilatation and contraction},
url = {http://eudml.org/doc/250635},
volume = {13},
year = {2009},
}

TY - JOUR
AU - Sagna, Abass
TI - Universal Ls-rate-optimality of Lr-optimal quantizers by dilatation and contraction
JO - ESAIM: Probability and Statistics
DA - 2009/6//
PB - EDP Sciences
VL - 13
SP - 218
EP - 246
AB - 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.
LA - eng
KW - Rate-optimal quantizers; empirical measure theorem; dilatation; Lloyd algorithm; rate-optimal quantizers; Gaussian distribution; Lloyd's algorithm
UR - http://eudml.org/doc/250635
ER -

References

top
  1. S. Delattre, S. Graf, H. Luschgy and G. Pagès, Quantization of probability distributions under norm-based distribution measures. Statist. Decisions22 (2004) 261–282.  Zbl1066.60026
  2. J.C. Fort and G. Pagès, Asymptotics of optimal quantizers for some scalar distributions. J. Comput. Appl. Math.146 (2002) 253–275.  Zbl1013.60004
  3. J.H. Friedman, J.L. Bentley and R.A. Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Trans. Math. Software3 (1977) 209–226.  Zbl0364.68037
  4. A. Gersho and R. Gray, Vector Quantization and Signal Compression, 6th edition. Kluwer, Boston (1992).  Zbl0782.94001
  5. S. Graf and H. Luschgy, Foundations of Quantization for Probability Distributions, Lect. Notes Math.1730. Springer, Berlin (2000).  Zbl0951.60003
  6. S. Graf, H. Luschgy and G. Pagès, Distorsion mismatch in the quantization of probability measures, ESAIM: PS12 (2008) 127–153.  Zbl1196.60062
  7. J. McNames, A Fast Nearest-Neighbor algorithm based on a principal axis search tree, IEEE Trans. Pattern Anal. Machine Intelligence23 (2001) 964–976.  
  8. G. Pagès, Space vector quantization method for numerical integration, J. Comput. Appl. Math.89 (1998) 1–38.  Zbl0908.65012
  9. G. Pagès, H. Pham and J. Printems, An Optimal markovian quantization algorithm for multidimensional stochastic control problems, Stochastics and Dynamics4 (2004) 501–545.  Zbl1111.65006
  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.  Zbl1138.91467

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.