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 -