Asymptotically optimal block quantization

Abstract

In 1948 W. R. Bennett used a companding model for nonuniform quantization and proposed the formulaD \: = \: \frac{1}{12N^{2}} \: \int \: p(x) [ É(x) ]^{-2} \dxfor the mean-square quantizing error whereNis the number of levels,p(x) is the probability density of the input, andE \prime(x) is the slope of the compressor curve. The formula, an approximation based on the assumption that the number of levels is large and overload distortion is negligible, is a useful tool for analytical studies of quantization. This paper gives a heuristic argument generalizing Bennett's formula to block quantization where a vector of random variables is quantized. The approach is again based on the asymptotic situation whereN, the number of quantized output vectors, is very large. Using the resulting heuristic formula, an optimization is performed leading to an expression for the minimum quantizing noise attainable for any block quantizer of a given block sizek. The results are consistent with Zador's results and specialize to known results for the one- and two-dimensional cases and for the case of infinite block length(k \rightarrow \infty). The same heuristic approach also gives an alternate derivation of a bound of Elias for multidimensional quantization. Our approach leads to a rigorous method for obtaining upper bounds on the minimum distortion for block quantizers. In particular, fork = 3we give a tight upper bound that may in fact be exact. The idea of representing a block quantizer by a block "compressor" mapping followed with an optimal quantizer for uniformly distributed random vectors is also explored. It is not always possible to represent an optimal quantizer with this block companding model.