Variable-Length Compression Allowing Errors
Abstract
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: (1-ε)kH(S) - √kV(S)/2π e – (Q^(-1)(ε))^2/2 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.
Additional Information
© 2015 IEEE. This work was supported in part by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under Grant CCF-0939370.Attached Files
Submitted - 1402.0608.pdf
Files
Name | Size | Download all |
---|---|---|
md5:046c24a9e4ea3cee60c0675c0b2b7801
|
415.5 kB | Preview Download |
Additional details
- Eprint ID
- 59088
- DOI
- 10.1109/ISIT.2014.6875320
- Resolver ID
- CaltechAUTHORS:20150730-142923980
- CCF-0939370
- NSF
- Created
-
2015-08-06Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field