×

Foundations of quantization for probability distributions. (English) Zbl 0951.60003

Lecture Notes in Mathematics. 1730. Berlin: Springer. x, 230 p. (2000).
The monograph provides the first systematic mathematical treatment of the following quantization problem: let \(\|\cdot\|\) be a norm on \(\mathbb{R}^d\), \(P\) a probability measure on \(\mathbb{R}^d\), \(n\in\mathbb{N}\), and \(r\geq 1\). Then \[ V_{n,r}(P): =\inf\Bigl\{\int \min_{a\in S}\|x-a\|^r dP(x):S\subset \mathbb{R}^d,\;|S|\leq n\Bigr\} \] is called the quantization error of \(P\). It measures how well \(P\) can be approximated by a probability measure which is supported by \(n\) points. The problem of computing \(V_{n,r}(P)\) and determining a minimizing set \(S\) is of great importance, e.g. in engineering (signal compression) and operations research (optimal location of service centers). Since precise values of \(V_{n,r}(P)\) and exact minimizers \(S\) are known only in a few special cases, estimates and asymptotic studies for large \(n\) are relevant.
In the first chapter the authors provide general properties of quantization, for example sufficient conditions for existence and uniqueness of minimizing sets \(S\). Chapter 2 treats asymptotics in case \(P\) is nonsingular w.r.t. Lebesgue measure. Theorem 6.2 states that under a slight moment condition, \(n^{r/d} V_{n,r}(P)\) converges as \(n\to\infty\) and a formula of the limit is provided in terms of a norm of the density of the absolutely continuous part \(P_a\) of \(P\). For any sequence \(S_n\) of asymptotically minimizing sets it is shown in Theorem 7.5 that the associated empirical measure converges weakly to some measure \(P_r\), whose density is given in terms of the density of \(P_a\). There is also a section on random quantizers in which \(S=\{Y_1, \dots,Y_n\}\), where \(Y_1,\dots, Y_n\) are i.i.d. The third chapter contains a number of recent results by the authors on the asymptotics for singular probability measures on \(\mathbb{R}^d\).
The lecture note is a well-written, detailed and comprehensive exposition of the state-of-the-art of the quantization problem for probability measures on \(\mathbb{R}^d\).

MSC:

60-02 Research exposition (monographs, survey articles) pertaining to probability theory
60E05 Probability distributions: general theory
PDFBibTeX XMLCite
Full Text: DOI