On the Wyner-Ziv problem for individual sequences
<|reference_start|>On the Wyner-Ziv problem for individual sequences: We consider a variation of the Wyner-Ziv 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 $\ell$ 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 $(\log M)/\ell$, 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$.<|reference_end|>
@article{merhav2005on,
    title={On the Wyner-Ziv problem for individual sequences},
    author={Neri Merhav and Jacob Ziv},
    journal={arXiv preprint arXiv:cs/0505010},
    year={2005},
    number={CCIT Report #517, Department of Electrical Engineering, Technion,
  February 2005},
    archivePrefix={arXiv},
    eprint={cs/0505010},
    primaryClass={cs.IT math.IT}
}