An information theoretic model for adaptive lossy compression

We investigate the underlying mechanism of universal sequential, fixed distortion, lossy source coding algorithms, through the “eyes” of a random code. We model the adaptive codebook as a “mixed type” random code whose codeword type distribution evolves with time while its dimension goes to infinity. The evolution law in our model has a structure of a tree; a type inherits its frequency in the code from its parent-types matching probabilities. We find that this mechanism naturally selects the “good” codeword types for compressing the (unknown) source. As a consequence, the code becomes optimal for the source, and approaches the rate-distortion function as the time, and hence the dimension, go to infinity. Beyond its analytical interest, this model also provides guidelines for developing lossy string matching (Lempel-Ziv-like) algorithms