TY - GEN

T1 - Fixed-length lossy compression in the finite blocklength regime

T2 - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

AU - Kostina, Victoria

AU - Verdu, Sergio

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Shannon theory

KW - achievability

KW - converse

KW - finite blocklength regime

KW - lossy source coding

KW - memoryless sources

KW - rate distortion

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

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

U2 - 10.1109/ISIT.2011.6034159

DO - 10.1109/ISIT.2011.6034159

M3 - Conference contribution

AN - SCOPUS:80054805681

SN - 9781457705953

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 41

EP - 45

BT - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

Y2 - 31 July 2011 through 5 August 2011

ER -