On Empirical Cumulant Generating Functions of Code Lengths for Individual Sequences
From MaRDI portal
Publication:4566601
DOI10.1109/TIT.2017.2757495zbMATH Open1390.94881arXiv1605.01182OpenAlexW2759836910MaRDI QIDQ4566601FDOQ4566601
Authors: Neri Merhav 
Publication date: 27 June 2018
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: We consider the problem of lossless compression of individual sequences using finite-state (FS) machines, from the perspective of the best achievable empirical cumulant generating function (CGF) of the code length, i.e., the normalized logarithm of the empirical average of the exponentiated code length. Since the probabilistic CGF is minimized in terms of the R'enyi entropy of the source, one of the motivations of this study is to derive an individual-sequence analogue of the R'enyi entropy, in the same way that the FS compressibility is the individual-sequence counterpart of the Shannon entropy. We consider the CGF of the code-length both from the perspective of fixed-to-variable (F-V) length coding and the perspective of variable-to-variable (V-V) length coding, where the latter turns out to yield a better result, that coincides with the FS compressibility. We also extend our results to compression with side information, available at both the encoder and decoder. In this case, the V-V version no longer coincides with the FS compressibility, but results in a different complexity measure.
Full work available at URL: https://arxiv.org/abs/1605.01182
Cited In (1)
This page was built for publication: On Empirical Cumulant Generating Functions of Code Lengths for Individual Sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566601)
