Third-Order Asymptotics of Variable-Length Compression Allowing Errors
Abstract
This study investigates the fundamental limits of variable-length compression in which prefix-free constraints are not imposed (i.e., one-to-one codes are studied) and non-vanishing error probabilities are permitted. Due in part to a crucial relation between the variable-length and fixed-length compression problems, our analysis requires a careful and refined analysis of the fundamental limits of fixed-length compression in the setting where the error probabilities are allowed to approach either zero or one polynomially in the blocklength. To obtain the refinements, we employ tools from moderate deviations and strong large deviations. Finally, we provide the third-order asymptotics for the problem of variable-length compression with non-vanishing error probabilities. We show that unlike several other information-theoretic problems in which the third-order asymptotics are known, for the problem of interest here, the third-order term depends on the permissible error probability.
Additional Information
© 2021 IEEE. Manuscript received July 16, 2020; revised September 14, 2021; accepted September 29, 2021. Date of publication October 4, 2021; date of current version November 22, 2021. This work was supported in part by the Singapore National Research Foundation (NRF) Fellowship under Grant R-263-000-D02-281 and in part by JSPS KAKENHI under Grant JP 21K21291. An earlier version of this paper was presented in part at the 2020 International Symposium on Information Theory and Its Applications (ISITA).Attached Files
Accepted Version - 2007.05147.pdf
Files
Name | Size | Download all |
---|---|---|
md5:48ca9731a58f56876e7cec1cebb3c1ea
|
333.4 kB | Preview Download |
Additional details
- Eprint ID
- 112668
- DOI
- 10.1109/tit.2021.3117591
- Resolver ID
- CaltechAUTHORS:20220104-618420500
- R-263-000-D02-281
- National Research Foundation (Singapore)
- JP 21K21291
- Japan Society for the Promotion of Science (JSPS)
- Created
-
2022-01-04Created from EPrint's datestamp field
- Updated
-
2022-01-04Created from EPrint's last_modified field