A universal scheme for wynerziv coding of discrete sources

Shirin Jalali; Sergio Verdú; Tsachy Weissman

doi:10.1109/TIT.2010.2040889

A universal scheme for wynerziv coding of discrete sources

Shirin Jalali, Sergio Verdú, Tsachy Weissman

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

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.

Original language	English (US)
Article number	5437417
Pages (from-to)	1737-1750
Number of pages	14
Journal	IEEE Transactions on Information Theory
Volume	56
Issue number	4
DOIs	https://doi.org/10.1109/TIT.2010.2040889
State	Published - Apr 2010

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Discrete denoising
Rate-distortion function
Sliding-window coding
Universal algorithm
Wyner-Ziv coding

Access to Document

10.1109/TIT.2010.2040889

Cite this

@article{0f16ce13c52646d98b82e693d41ea14b,

title = "A universal scheme for wynerziv coding of discrete sources",

abstract = "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.",

keywords = "Discrete denoising, Rate-distortion function, Sliding-window coding, Universal algorithm, Wyner-Ziv coding",

author = "Shirin Jalali and Sergio Verd{\'u} and Tsachy Weissman",

note = "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{\'u} 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: shirin@caltech.edu). S. Verd{\'u} is with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: verdu@princeton.edu). T. Weissman is with the Department of Electrical Engineering, Stanford University, Stanford, CA 94305 USA (e-mail: tsachy@stanford.edu). 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",

year = "2010",

month = apr,

doi = "10.1109/TIT.2010.2040889",

language = "English (US)",

volume = "56",

pages = "1737--1750",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "4",

}

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: shirin@caltech.edu). S. Verdú is with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: verdu@princeton.edu). T. Weissman is with the Department of Electrical Engineering, Stanford University, Stanford, CA 94305 USA (e-mail: tsachy@stanford.edu). 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 -

A universal scheme for wynerziv coding of discrete sources

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this