Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2017 | Submitted
Journal Article Open

Data Compression with Low Distortion and Finite Blocklength

Abstract

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.

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

Attached Files

Submitted - 1510.02190.pdf

Files

1510.02190.pdf
Files (459.6 kB)
Name Size Download all
md5:afefcca96298ee478ceaef27cffcd6f3
459.6 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 24, 2023