A zero-delay sequential quantizer for individual sequences
Tamás Linder, Gábor Lugosi · 2002
We consider adaptive sequential lossy coding of bounded individual sequences. The encoder and the decoder are connected via a noiseless channel of capacity R and both are assumed to have zero delay. No probabilistic assumptions are made on how the sequence to be encoded is generated. For any bounded sequence of length n, the distortion redundancy is defined as the normalized cumulative squared distortion of the sequential scheme minus the normalized cumulative squared distortion of the best scalar quantizer of rate R which is matched to this particular sequence. We demonstrate the existence of a zero-delay sequential scheme which uses common randomization in the encoder and the decoder such that the normalized maximum distortion redundancy converges to zero at a rate n/sup -1/5/logn.