TY - JOUR
T1 - A universal scheme for wynerziv coding of discrete sources
AU - Jalali, Shirin
AU - Verdú, Sergio
AU - Weissman, Tsachy
N1 - Funding Information:
Manuscript received February 28, 2008; revised November 19, 2009. Current version published March 17, 2010. The work of S. Jalali was supported by Stanford Graduate Fellowship. The work of S. Verdú was supported by the NSF under Grant CCR-0312839, National Science Foundation, Theoretical Foundations Research Grants CCF-0635154 and CCF-0728445. The work of T. Weissman was supported by an NSF CAREER grant. S. Jalali is with the Center for the Mathematics of Information, California Institute of Technology, Pasadena, CA 91125 USA (e-mail: [email protected]). S. Verdú is with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: [email protected]). T. Weissman is with the Department of Electrical Engineering, Stanford University, Stanford, CA 94305 USA (e-mail: [email protected]). Communicated by H. Yamamoto, Associate Editor for Shannon Theory. Color version of Figure 1 in this paper is available online at http://ieeexplore. ieee.org. Digital Object Identifier 10.1109/TIT.2010.2040889
PY - 2010/4
Y1 - 2010/4
N2 - We consider the WynerZiv (WZ) problem of lossy compression where the decompressor observes a noisy version of the source, whose statistics are unknown. A new family of WZ coding algorithms is proposed and their universal optimality is proven. Compression consists of sliding-window processing followed by LempelZiv (LZ) compression, while the decompressor is based on a modification of the discrete universal denoiser (DUDE) algorithm to take advantage of side information. The new algorithms not only universally attain the fundamental limits, but also suggest a paradigm for practical WZ coding. The effectiveness of our approach is illustrated with experiments on binary images, and English text using a low complexity algorithm motivated by our class of universally optimal WZ codes.
AB - We consider the WynerZiv (WZ) problem of lossy compression where the decompressor observes a noisy version of the source, whose statistics are unknown. A new family of WZ coding algorithms is proposed and their universal optimality is proven. Compression consists of sliding-window processing followed by LempelZiv (LZ) compression, while the decompressor is based on a modification of the discrete universal denoiser (DUDE) algorithm to take advantage of side information. The new algorithms not only universally attain the fundamental limits, but also suggest a paradigm for practical WZ coding. The effectiveness of our approach is illustrated with experiments on binary images, and English text using a low complexity algorithm motivated by our class of universally optimal WZ codes.
KW - Discrete denoising
KW - Rate-distortion function
KW - Sliding-window coding
KW - Universal algorithm
KW - Wyner-Ziv coding
UR - http://www.scopus.com/inward/record.url?scp=77950209807&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77950209807&partnerID=8YFLogxK
U2 - 10.1109/TIT.2010.2040889
DO - 10.1109/TIT.2010.2040889
M3 - Article
AN - SCOPUS:77950209807
SN - 0018-9448
VL - 56
SP - 1737
EP - 1750
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 4
M1 - 5437417
ER -