A Caltech Library Service

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

Kostina, Victoria and Verdú, Sergio (2011) Fixed-length lossy compression in the finite blocklength regime: discrete memoryless sources. In: IEEE International Symposium on Information Theory (ISIT), 2011. IEEE , Piscataway, NJ, pp. 41-45. ISBN 978-1-4577-0596-0.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Kostina, Victoria0000-0002-2406-7440
Alternate Title:Fixed-length lossy compression in the finite blocklength regime
Additional Information:© 2011 IEEE. This work was partially supported by NSF under grant CCF-1016625 and by the Center for Science of Information, an NSF Science and Technology Center, under grant agreement CCF-0939370. The first author was supported in part by the Natural Sciences and Engineering Research Council of Canada. Useful discussions with Dr. Yury Polyanskiy are gratefully acknowledged. In particular, Theorem 3 arose from discussions with him.
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Subject Keywords:Shannon theory, lossy source coding, rate distortion, memoryless sources, finite blocklength regime, achievability, converse.
Record Number:CaltechAUTHORS:20140910-110253022
Persistent URL:
Official Citation:Kostina, V.; Verdu, S., "Fixed-length lossy compression in the finite blocklength regime: Discrete memoryless sources," Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on , vol., no., pp.41,45, July 31 2011-Aug. 5 2011 doi: 10.1109/ISIT.2011.6034159
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49541
Deposited By: Ruth Sustaita
Deposited On:10 Sep 2014 18:24
Last Modified:03 Oct 2019 07:14

Repository Staff Only: item control page