Towards Empirical Sandwich Bounds on the Rate-Distortion Function
Towards Empirical Sandwich Bounds on the Rate-Distortion Function
复制标题
DOI：
--
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Yibo Yang;S. Mandt
中科院分区：
文献类型：
--
作者：
Yibo Yang;S. Mandt
率失真（R-D）函数是信息论中的一个关键量，它表征了任何压缩算法在保真度标准下可以压缩多少数据源的基本限制。随着研究人员不断提高压缩性能，建立给定数据源的R-D函数不仅具有科学意义，而且还揭示了改进压缩算法的可能空间。以前关于这个问题的工作依赖于数据源的分布假设（Gibson, 2017）或仅适用于离散数据（Blahut, 1972; Arimoto, 1972）。相比之下，本文首次尝试了一种算法，该算法将只需要i.d数据样本的一般（不一定是离散的）源的R-D函数夹在一起。我们估计了各种人工和现实世界数据源的R-D三明治边界，其设置远远超出了任何已知方法的可行性，并阐明了神经数据压缩的最优性（Ball\'e等人，2021；Yang等人，2022）。我们在自然图像上的R-D上限表明，在各种比特率下，改进最先进的图像压缩方法的PSNR至少为一个dB的理论空间。我们的数据和代码可以在https://github.com/mandt-lab/empirical-RD-sandwich上找到。
Rate-distortion (R-D) function, a key quantity in information theory, characterizes the fundamental limit of how much a data source can be compressed subject to a fidelity criterion, by any compression algorithm. As researchers push for ever-improving compression performance, establishing the R-D function of a given data source is not only of scientific interest, but also sheds light on the possible room for improving compression algorithms. Previous work on this problem relied on distributional assumptions on the data source (Gibson, 2017) or only applied to discrete data (Blahut, 1972; Arimoto, 1972). By contrast, this paper makes the first attempt at an algorithm for sandwiching the R-D function of a general (not necessarily discrete) source requiring only i.i.d. data samples. We estimate R-D sandwich bounds for a variety of artificial and real-world data sources, in settings far beyond the feasibility of any known method, and shed light on the optimality of neural data compression (Ball\'e et al., 2021; Yang et al., 2022). Our R-D upper bound on natural images indicates theoretical room for improving state-of-the-art image compression methods by at least one dB in PSNR at various bitrates. Our data and code can be found at https://github.com/mandt-lab/empirical-RD-sandwich.