A Caltech Library Service

Data Compression with Low Distortion and Finite Blocklength

Kostina, Victoria (2017) Data Compression with Low Distortion and Finite Blocklength. IEEE Transactions on Information Theory, 63 (7). pp. 4268-4285. ISSN 0018-9448.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper considers lossy source coding of n-dimensional memoryless sources and shows an explicit approximation to the minimum source coding rate required to sustain the probability of exceeding distortion d no greater than ϵ, which is simpler than known dispersion-based approximations. Our approach takes inspiration in the celebrated classical result stating that the Shannon lower bound to rate-distortion function becomes tight in the limit d → 0. We formulate an abstract version of the Shannon lower bound that recovers both the classical Shannon lower bound and the rate-distortion function itself as special cases. Likewise, we show that a nonasymptotic version of the abstract Shannon lower bound recovers all previously known nonasymptotic converses. A necessary and sufficient condition for the Shannon lower bound to be attained exactly is presented. It is demonstrated that whenever that condition is met, the rate-dispersion function is given simply by the varentropy of the source. Remarkably, all finite alphabet sources with balanced distortion measures satisfy that condition in the range of low distortions. Most continuous sources violate that condition. Still, we show that lattice quantizers closely approach the nonasymptotic Shannon lower bound, provided that the source density is smooth enough and the distortion is low. This implies that fine multidimensional lattice coverings are nearly optimal in the rate-distortion sense even at finite . The achievability proof technique is based on a new bound on the output entropy of lattice quantizers in terms of the differential entropy of the source, the lattice cell size, and a smoothness parameter of the source density. The technique avoids both the usual random coding argument and the simplifying assumption of the presence of a dither signal.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ItemConference Paper
Kostina, Victoria0000-0002-2406-7440
Additional Information:© 2017 IEEE. Manuscript received January 3, 2016; revised December 15, 2016; accepted January 30, 2017. Date of publication March 1, 2017; date of current version June 14, 2017. This work was supported in part by the National Science Foundation under Grant CCF-1566567 and in part by the Simons Institute for the Theory of Computing. This paper was presented at the Allerton Conference [1], [2].
Funding AgencyGrant Number
Simons Institute for the Theory of ComputingUNSPECIFIED
Subject Keywords:Lossy source coding, lattice coding, rate-distortion function, Shannon’s lower bound, low distortion, high resolution, finite blocklength regime, dispersion, rate-dispersion function, nonasymptotic analysis
Issue or Number:7
Record Number:CaltechAUTHORS:20170308-161418854
Persistent URL:
Official Citation:V. Kostina, "Data Compression With Low Distortion and Finite Blocklength," in IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4268-4285, July 2017. doi: 10.1109/TIT.2017.2676811
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74946
Deposited By: Kristin Buxton
Deposited On:09 Mar 2017 00:23
Last Modified:04 Oct 2019 20:09

Repository Staff Only: item control page