A Rigorous Approach to High-Resolution Entropy-Constrained Vector Quantization

Abstract

The nonnegativity of relative entropy implies that the differential entropy of a random vector X with probability density function (pdf) f is upper-bounded by -E[log g(X)]for any arbitrary pdf g. Using this inequality with a cleverly chosen g, we derive a lower bound on the asymptotic excess rate of entropy-constrained vector quantization for d-dimensional sources and rth-power distortion, where the asymptotic excess rate is defined as the difference between the smallest output entropy of a vector quantizer satisfying the distortion constraint and the rate-distortion function in the limit as the distortion tends to zero. Specialized to the one-dimensional case, this lower bound coincides with the asymptotic excess rate achieved by a uniform quantizer, thereby recovering the result by Gish and Pierce that uniform quantizers are asymptotically optimal as the allowed distortion tends to zero. Furthermore, in the one-dimensional case, the derivation of the lower bound reveals a necessary condition for a sequence of quantizers to be asymptotically optimal. This condition implies that any sequence of asymptotically optimal almost-regular quantizers must converge to a uniform quantizer as the distortion tends to zero. While the obtained lower bound itself is not novel, to the best of our knowledge, we present the first rigorous derivation that follows the direct approach by Gish and Pierce without resorting to heuristic high-resolution approximations commonly found in the quantization literature. Furthermore, our derivation holds for all d-dimensional sources having finite differential entropy and whose integer part has finite entropy. In contrast to Gish and Pierce, we do not require additional constraints on the continuity or decay of the source pdf. ; This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement number 714161), from the 7th European Union Framework Programme under Grant 333680, from the Ministerio de Economía y Competitividad of Spain under Grants TEC2013-41718-R, RYC-2014-16332, IJCI-2015-27020, TEC2015-69648-REDC, and TEC2016-78434-C3-3-R (AEI/FEDER, EU), and from the Comunidad de Madrid under Grant S2103/ICE-2845. The material in this paper was presented in part at the 2016 IEEE International Symposium on Information Theory, Barcelona, Spain, July 2016.