Lossless Data Compression with Side Information: Nonasymptotics and Dispersion
View / Open Files
Authors
Gavalakis, L
Kontoyiannis, I
Publication Date
2020Journal Title
IEEE International Symposium on Information Theory - Proceedings
Conference Name
2020 IEEE International Symposium on Information Theory (ISIT)
ISSN
2157-8095
ISBN
9781728164328
Publisher
IEEE
Volume
2020-June
Pages
2179-2183
Type
Conference Object
This Version
AM
Metadata
Show full item recordCitation
Gavalakis, L., & Kontoyiannis, I. (2020). Lossless Data Compression with Side Information: Nonasymptotics and Dispersion. IEEE International Symposium on Information Theory - Proceedings, 2020-June 2179-2183. https://doi.org/10.1109/ISIT44484.2020.9174326
Abstract
The problem of lossless data compression with side information available to both the encoder and the decoder is considered. The finite-blocklength fundamental limits of the best achievable performance are defined, in two different versions of the problem: Reference-based compression, when a single side information string is used repeatedly in compressing different source messages, and pair-based compression, where a different side information string is used for each source message. General achievability and converse theorems are established. Nonasymptotic normal approximation expansions are proved for the optimal rate with memoryless sources, in both the reference-based and pair-based settings. These are stated in terms of explicit, finite-blocklength bounds, that are tight up to third-order terms. Extensions that go significantly beyond the class of memoryless sources are obtained. The relevant source dispersion is identified and its relationship with the conditional varentropy rate is established. Interestingly, the dispersion is different in reference-based and pair-based compression, and it is proved that the reference-based dispersion is in general smaller.
Identifiers
External DOI: https://doi.org/10.1109/ISIT44484.2020.9174326
This record's URL: https://www.repository.cam.ac.uk/handle/1810/332794
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.