Quantization for probability measures [Elektronische Ressource] / von Sanguo Zhu

Description

Quantization for probability measuresvon Sanguo ZhuDissertationzur Erlangung des Grades eines Doktors derNaturwissenschaften– Dr. rer. nat. –Vorgelegt im Fachbereich 3 (Mathematik & Informatik)der Universität Bremenim September 2005Datum des Promotionskolloquiums: 7. Dezember 2005.Gutachter: Prof. Dr. Marc Kesseböhmer (Universität Bremen)Prof. Dr. Siegfried Graf (Universität Passau)ContentsAbstract 5Introduction 7Chapter 1. Quantization numbers and limit quantization dimensions 131.1. Quantization numbers 131.2. Rate distortion dimension 151.3. Quantization dimension for product measures 161.4. Essential covering rate and the upper quantization dimension 171.5. Essential covering rate and limit quantization dimensions 25Chapter 2. Stability and stabilization of the upper quantization dimension 312.1. Preliminary concepts and facts 312.2. Stability and stabilization of dimensions for measures 332.3. Finite stability of the upper quantization dimension 362.4. Stabilization of the upper quantization dimension and coefficient 402.5. Quantization for homogeneous Cantor measures 452.6. Stability and stabilization of limit quantization dimension 60Chapter 3. Quantization and absolute continuity of measures 633.1. Preliminary facts 633.2. Box-counting dimension, vanishing rates and quantization 653.3. D () is not monotone and doesnot obey a variational law 72r3.4. Ahlfors-David regular measures 753.5.

Sujets

• Mathematics

Informations

• Publié par: universitat_bremen
• Publié le: 01 janvier 2005
• Nombre de lectures: 89
• Langue: English

Extrait

Quantization for probability measures

von Sanguo Zhu

Dissertation

zur Erlangung des Grades eines Doktors der

Naturwissenschaften

– Dr. rer. nat. –

Vorgelegt im Fachbereich 3 (Mathematik & Informatik)

der Universität Bremen

im September 2005

Datum des Promotionskolloquiums:

Gutachter:

7. Dezember 2005.

Prof. Dr. Marc Kesseböhmer (Universität Bremen) Prof. Dr. Siegfried Graf (Universität Passau)

Abstract

Introduction

Contents

Chapter 1. Quantization numbers and limit quantization dimensions 1.1. Quantization numbers 1.2. Rate distortion dimension 1.3. Quantization dimension for product measures 1.4. Essential covering rate and the upper quantization dimension 1.5. Essential covering rate and limit quantization dimensions

Chapter 2. Stability and stabilization of the upper quantization dimension 2.1. Preliminary concepts and facts 2.2. Stability and stabilization of dimensions for measures 2.3. Finite stability of the upper quantization dimension 2.4. Stabilization of the upper quantization dimension and coefcient 2.5. Quantization for homogeneous Cantor measures 2.6. Stability and stabilization of limit quantization dimension

Chapter 3. Quantization and absolute continuity of measures 3.1. Preliminary facts 3.2. Box-counting dimension, vanishing rates and quantization 3.3.D r ()is not monotone and doesnot obey a variational law 3.4. Ahlfors-David regular measures 3.5. Self-similar measures

Index

Bibliography

Acknowledgment

3

5

7

13 13 15 16 17 25

31 31 33 36

40 45 60

63 63

65 72 75

77

89

91

93

Abstract

We introduce the notions of quantization number and essential covering rate. Using these notions, we treat the quantization for product measures and give effective up- per bounds for the quantization dimension of measures - especially for those with unbounded support. We also introduce the concepts of complete moment condition and limit quantization dimension and study the interesting cases where ther-moment condition holds for allr≥1.

We then introduce the notions of stability and stabilization for dimensions of measures. Under this framework, we study the stability of the upper and lower quantization di- mension. Several examples are given. We prove that the stabilized upper quantization dimension coincides with the packing dimension, and for measures with compact sup- port, it also coincides with the stabilized upper box counting-dimension. The quanti- zation for homogeneous Cantor measures are particularly studied in detail to construct examples showing that the lower quantization dimension is not nitely stable.

We nally introduce the concept of the upper and lower vanishing rates. Using this concept and the upper and lower box-counting dimension, we study the relationship between the quantization and absolute continuity of measures. We give several suf- cient conditions to ensure a denite inequality between thequantization dimension of two measures one of which is absolutely continuous with respect to the other. Mea- sures which are absolutely continuous with respect to self-similar measures are partic- ularly studied. A stronger result regarding the quantization coefcient is obtained as an analogue to the case of nite-dimensional Lebesgue measures.

5

Introduction

Quantization problems originate in information theory and engineering technology such as image compression and data processing. The study of this eld goes back to the 1940's. Mathematically, the aim of quantization is to approximate a given prob- ability measure by discrete probability measures with nite supports. Letr≥1and  1   2 be Borel probability measures onR d with R kxk r d i (x)<∞ i= 12. We denote byM( 1   2 )the set of all Borel probability measures onR d ×R d with the i-th marginal i  i= 12. Dene ρ r ( 1   2 ) := inf Z kx−yk r dν(x y) :ν∈ M( 1   2 )  1r 

ρ r ()denes a metric on the set of Borel probability measures onR d with ther- moment condition R kxk r d(x)<∞, which is calledL r -minimal metric. Now letbe a Borel probability measure onR d and letP n denote the set of all discrete probability measuresQonR d withcard (supp (Q))≤n the. Denen-thquantization r errorofof orderrbye nr () :=V n 1 r  (), where

V nr () := inf{ρ r r ( Q) :Q∈ P n }

If the above inmum is attained at someQ∈ P n , we then callQann-optimal proba- bility measure since this measure best approximateswith respect to theL r -minimal metric. By [9, Lemma 6.1 ], iffullls ther-moment condition R kxk r d(x)<∞ then the quantization errore nr ()tends to zero asn The rate attends to innity. whiche nr ()tends to zero gives good information about how well the measurecan be approximated by discrete measures with nite support. A good way to characterize this convergence rate is to consider theupperandlower quantization dimensionof. Dene (0.0.1)D r () := li n m → s ∞ up −log ol e g n n r ()  D r () := li n m → i ∞ nf − l olg o e g n n r () 

We callD r () D r ()the upper and lower quantization dimension ofof order r. IfD r ()coincides withD r ()then we call the common value the quantization, dimension ofof orderrand denote it byD r ().

7

8

INTRODUCTION

The upper and lower quantization dimension ofoforder innityD ∞ () D ∞ ()are dened similarly by replacinge nr ()withe n∞ ()given by (0.0.2)e n∞ () := inf ( x∈s s u u p p p() a m ∈ i α nkx−ak:α⊂R d card(α)≤n ) 

The quantitye n∞ ()is called then-thcovering radiusofsupp(). Whenever we considerD ∞ () D ∞ (), we assume thatsupp() Letis compact.dim B dim B re- spectively denote the upper and lower box-counting dimension of sets. Among other signicant properties, it is shown in [9] that

(0.0.3)

D ∞ () = dim B (supp()) D ∞ () = dim B (supp())

The notion of quantization dimension was rst introduced by Z ADOR (cf. [26]). In this thesis, we will further study some basic properties of the quantization dimension,

including the range and bounds of the quantization dimension and the quantization dimension for product measures. For this purpose we will introduce in chapter 1 the notion of quantization numbers and that of essential covering rate. These notions will also be used to prove an inequality between the upper quantization dimension and the upper rate distortion dimension.

The upper and lowers-dimensionalquantization coefcientof orderrare respectively dened by

Q r s () := lim supn rs V nr () Q r s () := li n m → i ∞ nfn rs V nr () n→∞ When they coincide, we call the common value thes-dimensional quantization coef- cient ofof orderrand denote it byQ s r ().

In accordance with the main aim of quantization, people are concerned with the fol- lowing two objectives. The rst objective is to seek for eachn∈Nthen-optimal probability measure, which best approximatesthe second is to study the asymp-; totic property of the quantization error, including the calculation of the quantization dimension and the estimate of the quantization coefcient. We shall study in detail the quantization for the uniform probability measures on homogeneous Cantor sets and achieve these goals under some suitable conditions (cf. chapter 2). We remark that there are several equivalent denitions of the quantization error (cf. [9 may]). One go back and forth among these equivalent denitions and choose for each context the most suitable one. We state here one of the equivalent denitions which we will use frequently in this thesis.

(0.0.4)

V nr () = inf Z

nk r d(x) : a m ∈ i α kx−a

α⊂R d card (α)≤n 



INTRODUCTION

9

If the inmum in (0.0.4) is attained for someα⊂R d withcard (α)≤n, we then call αann-optimal set ofof orderr. The collection of alln-optimal sets ofof orderr is denoted byC nr ().

In the following, we recall some recent progress in quantization theory which is closely connected to this work.

Z ADOR (cf. [27]), B UCKLEW and W ISE ([2) proved that if a probability measure]  onR d has compact support and its absolutely continuous part does not vanish, then Q r d () =C(r d)  λd d d  d d +  r whereC(r d)is a positive constant depending only onrandd result is then. This proved valid for probability measuresnot necessarily with compact support but ful- lling the(r+δ)-moment condition (cf. [9 all absolutely con-, Theorem 6.2]). So tinuous measures fullling the(r+δ)-moment condition behave nicely with respect to their quantization properties. The only one drawback is that the constantC(r d) is only known for very few special cases and quite difcult tocalculate. We study in Chapter 3 the relationship between quantization and absolute continuity of measures. We especially study those measures which are singular with respect to Lebesgue mea- sure. Several counterexamples are constructed and various conditions will be given there to ensure a denite inequality between the quantization dimensions of two mea- sures one of which is absolutely continuous with respect to the other.

G RAF and L USCHGY have studied in detail the quantization properties of self-similar measures under the open set condition (cf. [10, 7, 8]). These results were extended by L INDSAY and M AULDIN  [to self-conformal measures (cf.17]). In there, the au- thors point out the relationship between the quantization dimension for self-conformal measures and its multifractal spectrum. This shows that quantization theory should in some nice way be connected with fractal geometry. Indeed, according to [9], the upper (lower) quantization dimension of order innity coincideswith the upper (lower) box- counting dimension, which are two of the most popular fractal quantities. G RAF and L USCHGY even conjecture that the covering problem is just the limit of the quantiza- tion problem, while we know that fractal objects, like Hausdorff, packing dimensions and measures, the upper and lower box-counting dimensions are all dened in terms of coverings, packings, or partitions. Letdim ∗ H dim ∗ P dim ∗ B dim ∗ B respectively denote the Hausdorff, packing, upper and lower box-counting dimension of. Then G RAF and L USCHGY show in [9] that

dim ∗ H ≤D r ()≤D r ()≤D ∞ ()