Optimal Parametric Backward-Adaptive Lossy Compression ∗
Yuval Kochman, Ram Zamir · 2005
We present a new generic mechanism for “on-line ” construction of a vector quantizer codebook, based on blockwise backward-adaptive parametric encoding. The workings of the proposed scheme is explained by the principle of “natural type selection”: In the limit of large vector dimension, the type of the first distortion-matching codeword within a random codebook coincides with an iteration of the Blahut-Arimoto algorithm for computation of the ratedistortion function. We extend this observation to parametric codebooks, and demonstrate that the parameter sequence converges to an optimum solution within the reproduction class. In comparison to other methods, adaptation is simple due to the parametric model, yet it is optimal even in the low coding rate regime. Keywords: parametric encoding, natural type selection, Arimoto-Blahut algorithm, vector quantization, alternating minimization, universal coding, approximate string matching.