Fixed-length lossy compression in the finite blocklength regime: Discrete memoryless sources

Victoria Kostina, Sergio Verdu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

This paper studies the minimum achievable source coding rate as a function of blocklength n and tolerable distortion level d. Tight general achievability and converse bounds are derived that hold at arbitrary fixed blocklength. For stationary memoryless sources with separable distortion, the minimum rate achievable is shown to be q closely approximated by R(d) + √v(d)/nQ -1 (∈), where R(d) is the rate-distortion function, V (d) is the rate dispersion, a characteristic of the source which measures its stochastic variability, Q-1 (•) is the inverse of the standard Gaussian complementary cdf, and ∈ is the probability that the distortion exceeds d. The new bounds and the second-order approximation of the minimum achievable rate are evaluated for the discrete memoryless source with symbol error rate distortion. In this case, the second-order approximation reduces to R(d) +1/2 log n/n if the source is non-redundant.

Original languageEnglish (US)
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages41-45
Number of pages5
DOIs
StatePublished - 2011
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: Jul 31 2011Aug 5 2011

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8104

Other

Other2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Country/TerritoryRussian Federation
CitySt. Petersburg
Period7/31/118/5/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Keywords

  • Shannon theory
  • achievability
  • converse
  • finite blocklength regime
  • lossy source coding
  • memoryless sources
  • rate distortion

Fingerprint

Dive into the research topics of 'Fixed-length lossy compression in the finite blocklength regime: Discrete memoryless sources'. Together they form a unique fingerprint.

Cite this