Nonlinear sparse-graph codes for lossy compression

Ankit Gupta; Sergio Verdú

doi:10.1109/TIT.2009.2016040

Nonlinear sparse-graph codes for lossy compression

Ankit Gupta, Sergio Verdú

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

27 Scopus citations

Abstract

We propose a scheme for lossy compression of discrete memoryless sources: The compressor is the decoder of a nonlinear channel code, constructed from a sparse graph. We prove asymptotic optimality of the scheme for any separable (letter-by-letter) bounded distortion criterion. We also present a suboptimal compression algorithm, which exhibits near-optimal performance for moderate block lengths.

Original language	English (US)
Pages (from-to)	1961-1975
Number of pages	15
Journal	IEEE Transactions on Information Theory
Volume	55
Issue number	5
DOIs	https://doi.org/10.1109/TIT.2009.2016040
State	Published - 2009

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Discrete memoryless sources
Lossy data compression
Rate-distortion theory
Source-channel coding duality
Sparse-graph codes

Access to Document

10.1109/TIT.2009.2016040

Cite this

@article{c106868043ae45cd8b55fef2efa42b3e,

title = "Nonlinear sparse-graph codes for lossy compression",

abstract = "We propose a scheme for lossy compression of discrete memoryless sources: The compressor is the decoder of a nonlinear channel code, constructed from a sparse graph. We prove asymptotic optimality of the scheme for any separable (letter-by-letter) bounded distortion criterion. We also present a suboptimal compression algorithm, which exhibits near-optimal performance for moderate block lengths.",

keywords = "Discrete memoryless sources, Lossy data compression, Rate-distortion theory, Source-channel coding duality, Sparse-graph codes",

author = "Ankit Gupta and Sergio Verd{\'u}",

note = "Funding Information: Manuscript received June 24, 2007; revised January 08, 2009. Current version published April 22, 2009. This work was supported in part by the National Science Foundation under Grant CCR-0312839. The material in this paper was presented in part at the IEEE Information Theory Workshop, Lake Tahoe, CA, September 2007. The authors are with the Department of Electrical Engineering, Princeton University, Princeton NJ 08544 USA (e-mail:ankitg@princeton.edu; verdu@princeton.edu). Communicated by M. Effros, Associate Editor for Source Coding. Color versions of Figures 1–7 in this paper are available online at http://iee-explore.ieee.org. Digital Object Identifier 10.1109/TIT.2009.2016040",

year = "2009",

doi = "10.1109/TIT.2009.2016040",

language = "English (US)",

volume = "55",

pages = "1961--1975",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

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

number = "5",

}

TY - JOUR

T1 - Nonlinear sparse-graph codes for lossy compression

AU - Gupta, Ankit

AU - Verdú, Sergio

N1 - Funding Information: Manuscript received June 24, 2007; revised January 08, 2009. Current version published April 22, 2009. This work was supported in part by the National Science Foundation under Grant CCR-0312839. The material in this paper was presented in part at the IEEE Information Theory Workshop, Lake Tahoe, CA, September 2007. The authors are with the Department of Electrical Engineering, Princeton University, Princeton NJ 08544 USA (e-mail:ankitg@princeton.edu; verdu@princeton.edu). Communicated by M. Effros, Associate Editor for Source Coding. Color versions of Figures 1–7 in this paper are available online at http://iee-explore.ieee.org. Digital Object Identifier 10.1109/TIT.2009.2016040

PY - 2009

Y1 - 2009

N2 - We propose a scheme for lossy compression of discrete memoryless sources: The compressor is the decoder of a nonlinear channel code, constructed from a sparse graph. We prove asymptotic optimality of the scheme for any separable (letter-by-letter) bounded distortion criterion. We also present a suboptimal compression algorithm, which exhibits near-optimal performance for moderate block lengths.

AB - We propose a scheme for lossy compression of discrete memoryless sources: The compressor is the decoder of a nonlinear channel code, constructed from a sparse graph. We prove asymptotic optimality of the scheme for any separable (letter-by-letter) bounded distortion criterion. We also present a suboptimal compression algorithm, which exhibits near-optimal performance for moderate block lengths.

KW - Discrete memoryless sources

KW - Lossy data compression

KW - Rate-distortion theory

KW - Source-channel coding duality

KW - Sparse-graph codes

UR - http://www.scopus.com/inward/record.url?scp=65749088035&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=65749088035&partnerID=8YFLogxK

U2 - 10.1109/TIT.2009.2016040

DO - 10.1109/TIT.2009.2016040

M3 - Article

AN - SCOPUS:65749088035

SN - 0018-9448

VL - 55

SP - 1961

EP - 1975

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 5

ER -

Nonlinear sparse-graph codes for lossy compression

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this