On the Wyner-Ziv problem for individual sequences

DOI10.1109/TIT.2005.864434zbMATH Open1317.94063arXivcs/0505010MaRDI QIDQ3547389

Jacob Ziv, Neri Merhav

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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 $(logM)/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$.

Full work available at URL: https://arxiv.org/abs/cs/0505010

Mathematics Subject Classification ID

Source coding (94A29) Rate-distortion theory in information and communication theory (94A34)

This page was built for publication: On the Wyner-Ziv problem for individual sequences