TY - GEN
T1 - Variable-length compression allowing errors
AU - Kostina, Victoria
AU - Polyanskiy, Yury
AU - Verdu, Sergio
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - This paper studies the fundamental limits of the minimum average length of variable-length compression when a nonzero error probability ε is tolerated. We give non-asymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit which is quite accurate for all but small blocklengths: equation where Q-1 (·) is the functional inverse of the Q-function and V (S) is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of 1-ε, but also this asymptotic limit is approached from below, i.e. a larger source dispersion and shorter blocklengths are beneficial. Further, we show that variable-length lossy compression under excess distortion constraint also exhibits similar properties.
AB - This paper studies the fundamental limits of the minimum average length of variable-length compression when a nonzero error probability ε is tolerated. We give non-asymptotic bounds on the minimum average length in terms of Erokhin's rate-distortion function and we use those bounds to obtain a Gaussian approximation on the speed of approach to the limit which is quite accurate for all but small blocklengths: equation where Q-1 (·) is the functional inverse of the Q-function and V (S) is the source dispersion. A nonzero error probability thus not only reduces the asymptotically achievable rate by a factor of 1-ε, but also this asymptotic limit is approached from below, i.e. a larger source dispersion and shorter blocklengths are beneficial. Further, we show that variable-length lossy compression under excess distortion constraint also exhibits similar properties.
UR - http://www.scopus.com/inward/record.url?scp=84906534089&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906534089&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2014.6875320
DO - 10.1109/ISIT.2014.6875320
M3 - Conference contribution
AN - SCOPUS:84906534089
SN - 9781479951864
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2679
EP - 2683
BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 IEEE International Symposium on Information Theory, ISIT 2014
Y2 - 29 June 2014 through 4 July 2014
ER -