Backward Adaptive Quantization Can Approach the Rate Distortion Function

Ram Zamir, Tel Aviv University:

Thursday March 20, 2003, 4:30 PM, Princeton University, Friend 004

We present a new adaptive mechanism for empirical ``on-line'' design of a vector quantizer codebook. The proposed scheme is based on the principle of ``natural type selection'' (NTS), presented in a recent work by Zamir and Rose. The NTS principle implies that backward adaptation, i.e., adaptation directed by the past reconstruction rather than by the uncoded source sequence, converges to an optimum rate-distortion codebook. We incorporate the NTS iteration step into a parametric encoder. We demonstrate that the codebook converges to an optimum rate-distortion solution within the associated parametric class. This new scheme does not suffer from the severe complexity at high dimensions of non-parametric solutions like the generalized Lloyd algorithm (GLA). Moreover, unlike existing parametric adaptive schemes (e.g., code-excited linear prediction (CELP)), this scheme is optimal even for low coding rates. Joint work with Yuval Kochman.