On the Structure of Optimal Entropy-Constrained
András György, Tamás Linder · 2002
The nearest neighbor condition implies that when searching for a mean-square optimal fixed-rate quantizer it is enough to consider the class of quantizers, i.e., quantizers having convex cells and codepoints which lie inside the associated cells. In contrast, quantizer regularity can preclude optimality in entropy-constrained quantization. This can be seen by exhibiting a simple discrete scalar source for which the mean-square optimal entropy-constrained scalar quantizer (ECSQ) has disconnected (and hence nonconvex) cells at certain rates. In this work, new results concerning the structure and existence of optimal ECSQs are presented. One main result shows that for continuous sources and distortion measures of the form , where is a nondecreasing convex function, any finite-level ECSQ can be regularized so that the resulting quantizer has the same entropy and equal or less distortion. Regarding the existence of optimal ECSQs, we prove that under rather general conditions there exists an almost regular optimal ECSQ for any entropy constraint. For the squared error distortion measure and sources with piecewise-monotone and continuous densities, the existence of a optimal ECSQ is shown. tizer is essentially determined by its codepoints since its cells are the Voronoi regions (with respect to the source distribution) associated with the codepoints. For the squared error distor- tion measure this implies that an optimal quantizer is regular, i.e., each of its cells is a convex set and the associated code- point lies inside the cell. The cells of a scalar quan- tizer are intervals, and the cells of a vector quantizer with a finite number of codepoints are convex polytopes. In this sense, the structure of optimal fixed-rate quantizers for the squared error distortion measure (and to a certain extent for more general norm-based distortion measures (5)) is relatively well understood. Moreover, for reasonable distortion measures and source distributions, the distortion of a quantizer satisfying the nearest neighbor condition is a continuous function of its codepoints, and so the existence of optimal fixed-rate quantizers can be deduced using standard continuity-compactness argu-