Pointwise redundancy in lossy data compression and universal lossy data compression
Pointwise redundancy in lossy data compression and universal lossy data compression
复制标题
DOI：
10.1109/18.817514
复制
发表时间：
2000-01-01
影响因子：
2.5
通讯作者：
Kontoyiannis, I
中科院分区：
文献类型：
--
作者：
Kontoyiannis, I
我们表征了在固定失真水平下有损数据压缩的可实现的冗余率。 “点冗余”是指通过n阶块代码实现的描述长度与最佳NR（D）位之间的差异。对于无内存的来源，我们表明，最佳可实现的冗余率是概率O（root n）的顺序。这是从二阶的完善到经典源编码定理的形式，其形式为“单方面的中心限制”。此外，我们表明，（几乎）任何源实现，在失真级别D级运行的任何块代码的描述长度至少超过c根N log log n，无限频繁。还给出了相应的直接编码定理，表明这些速率基本上是可以实现的。上述速率与最近报道的各种作者最近报告的订单O（log n）的预期冗余速率形成鲜明对比。我们的方法基于表明，任意代码顺序的压缩性能基本上是由香农随机代码的性能限制的。我们获得了上述结果的部分概括，以记忆的任意来源，并且证明了“ Barron's Lemma”的有损类似物。
We characterize the achievable pointwise redundancy rates for lossy data compression at a fixed distortion level. "Pointwise redundancy" refers to the difference between the description length achieved by an nth-order block code and the optimal nR(D) bits. For memoryless sources, we show that the best achievable redundancy rate is of order O(root n) in probability. This follows from a second-order refinement to the classical source coding theorem, in the form of a "one-sided central limit theorem." Moreover, we show that, along (almost) any source realization, the description lengths of any sequence of block codes operating at distortion level D exceed nR(D) by at least as much as C root n log log n, infinitely often. Corresponding direct coding theorems are also given, showing that these rates are essentially achievable. The above rates are in sharp contrast with the expected redundancy rates of order O(log n) recently reported by various authors. Our approach is based on showing that the compression performance of an arbitrary sequence of codes is essentially bounded below by the performance of Shannon's random code. We obtain partial generalizations of the above results for arbitrary sources with memory, and we prove lossy analogs of "Barron's Lemma.".