论文标题
minimax利率渗透率
Minimax Rate-Distortion
论文作者
论文摘要
我们显示了几乎可以肯定地满足损坏约束的可变速率利率降低代码的存在，即相对于未知的源分布和仅在运行时揭示的不明源分布和失真度量，并且是非常普遍的。如果我们仅需要有关源分布而不是失真度量的最小值通用性，那么我们提供了可实现的$ \ tilde {o}（1/\ sqrt {n}）$冗余率，我们显示的是最佳的。这与先前在普遍有损压缩方面的工作相反，后者在各种规律性条件下为弱普遍代码提供$ O（\ log n/n）$冗余保证。我们表明，消除规律性条件或升级到强大的普遍性，同时保持这些规律性条件需要使冗余不可避免地增加到$ \ tilde {o} {o}（1/\ sqrt {n}）$。我们的结构涉及使用非I.I.D。\ codeWord和零速率未编码的传输方案进行随机编码。该证明使用了与大偏差，接受拒绝抽样和失真度量的VC维度相确切的渐近学。
We show the existence of variable-rate rate-distortion codes that meet the disortion constraint almost surely and are minimax, i.e., strongly, universal with respect to an unknown source distribution and a distortion measure that is revealed only to the encoder and only at runtime. If we only require minimax universality with respect to the source distribution and not the distortion measure, then we provide an achievable $\tilde{O}(1/\sqrt{n})$ redundancy rate, which we show is optimal. This is in contrast to prior work on universal lossy compression, which provides $O(\log n/n)$ redundancy guarantees for weakly universal codes under various regularity conditions. We show that either eliminating the regularity conditions or upgrading to strong universality while keeping these regularity conditions entails an inevitable increase in the redundancy to $\tilde{O}(1/\sqrt{n})$. Our construction involves random coding with non-i.i.d.\ codewords and a zero-rate uncoded transmission scheme. The proof uses exact asymptotics from large deviations, acceptance-rejection sampling, and the VC dimension of distortion measures.
