On the Wyner-Ziv problem for individual sequences

We consider a variation of the Wyner-Ziv (W-Z) problem pertaining to lossy compression of individual sequences using finite-state encoders and decoders. There are two main results in this paper. The first characterizes the relationship between the performance of the best M-state encoder-decoder pair to that of the best block code of size e for every input sequence, and shows that the loss of the latter relative to the former (in terms of both rate and distortion) never exceeds the order of (Iog M)/l, independently of the input sequence. Thus, in the limit of large M, the best rate-distortion performance of every infinite source sequence can be approached universally by a sequence of block codes (which are also implementable by finite-state machines). While this result assumes an asymptotic regime where the number of states is fixed, and only the length n of the input sequence grows without bound, we then consider the case where the number of states M = M-n is allowed to grow concurrently with n. Our second result is then about the critical growth rate of M-n such that the rate-distortion performance of M-n-state encoder-decoder pairs can still be matched by a universal code. We show that this critical growth rate of M-n is linear in n.