论文标题
尖锐的二阶角渐近造型，用于无损压缩和侧面信息
Sharp Second-Order Pointwise Asymptotics for Lossless Compression with Side Information
论文作者
论文摘要
当在编码器和解码器都可以使用相关的侧面信息时，检查了确定任意无损压缩算法的最佳性能性能的最佳性能的问题。对于任意源端信息对，有条件的信息密度显示为通过任意压缩机序列实现的描述长度提供了尖锐的渐近下限。这意味着，对于厄贡源端信息对，条件熵率是最佳可实现的渐近下限与该速率的最佳结合，不仅是预期的，而且是概率。在适当的混合条件下，证明了中心限制定理和迭代对数定律，描述了二阶渐近最佳速率的必然波动。在相同条件下，具有侧面信息的Lempel-Ziv编码的理想化版本在同一条件下是普遍的一阶和二阶的最佳选择。这些结果部分基于有条件信息密度的新的几乎纯净的不变性原则，这可能具有独立感兴趣。
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.
