arXiv Analytics

Sign in

arXiv:2005.10823 [cs.IT]AbstractReferencesReviewsResources

Sharp Second-Order Pointwise Asymptotics for Lossless Compression with Side Information

Lampros Gavalakis, Ioannis Kontoyiannis

Published 2020-05-21Version 1

The problem of determining the best achievable performance of arbitrary lossless compression algorithms is examined, when correlated side information is available at both the encoder and decoder. For arbitrary source-side information pairs, the conditional information density is shown to provide a sharp asymptotic lower bound for the description lengths achieved by an arbitrary sequence of compressors. This implies that, for ergodic source-side information pairs, the conditional entropy rate is the best achievable asymptotic lower bound to the rate, not just in expectation but with probability one. Under appropriate mixing conditions, a central limit theorem and a law of the iterated logarithm are proved, describing the inevitable fluctuations of the second-order asymptotically best possible rate. An idealised version of Lempel-Ziv coding with side information is shown to be universally first- and second-order asymptotically optimal, under the same conditions. These results are in part based on a new almost-sure invariance principle for the conditional information density, which may be of independent interest.

Related articles:
arXiv:0805.2995 [cs.IT] (Published 2008-05-20)
Lossless Compression with Security Constraints
arXiv:1304.7392 [cs.IT] (Published 2013-04-27)
A Universal Grammar-Based Code For Lossless Compression of Binary Trees