Abstract
The 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. Establishing the R-D function for real-world data is of significant scientific interest, as it reveals the potential room for improving existing compression algorithms. Previous methods relied on restrictive distributional assumptions or were limited to discrete data. This paper presents the first algorithm for "sandwiching" the R-D function of general, continuous sources using only i.i.d. data samples. By estimating these bounds across various artificial and real-world datasets, we demonstrate that state-of-the-art image compression methods still have at least 1 dB of PSNR room for improvement.
Introduction
In information theory, the Rate-Distortion function $R(D)$ represents the absolute minimum number of bits required to represent a data source for a given level of allowed distortion. For researchers in lossy compression, $R(D)$ is the ultimate benchmark: if an algorithm's performance matches the $R(D)$ curve, it has reached theoretical optimality.
However, for complex, high-dimensional data like natural images or speech, the true $R(D)$ function remains unknown. Classical tools like the Blahut-Arimoto algorithm are computationally infeasible for high-dimensional continuous data. Consequently, the field has lacked a rigorous way to measure the gap between current compression performance and the theoretical limit. This work addresses this gap by providing empirical upper and lower bounds—a "sandwich"—that contains the true $R(D)$ function.
Methodology: The Empirical Sandwich
The authors propose a two-pronged approach to bound the $R(D)$ function directly from data samples.
1. The Upper Bound via $\beta$-VAE
The researchers establish a theoretical connection between Variational Autoencoders (VAEs) and information theory. They prove that a $\beta$-VAE trained with a likelihood model corresponding to a specific distortion metric (e.g., Gaussian likelihood for Mean Squared Error) minimizes an upper bound on the $R(D)$ function. By utilizing highly expressive neural networks, the $\beta$-VAE can provide a tight empirical upper bound on the minimum rate required for a given distortion.
2. The Lower Bound via Dual Formulation
Establishing a lower bound is more challenging, as it requires proving that no possible algorithm can achieve a lower rate. The authors utilize a dual mathematical characterization of $R(D)$, transforming it into an unconstrained optimization problem. To handle the resulting complexity, they employ a $k$-sample estimator inspired by Importance Weighted Autoencoders (IWAE), allowing the lower bound to be optimized using standard stochastic gradient ascent.
Experimental Validation
The methodology was validated across synthetic and real-world datasets, including high-dimensional Gaussians, particle physics data, and speech spectrograms.
As shown in the experimental results, the proposed method successfully sandwiches the $R(D)$ function. In the case of 1000-dimensional Gaussian sources, the empirical upper bound converges precisely to the known analytical solution. For more complex data like speech (33-dimensional spectrograms) and particle physics data, the bounds create a clear "red zone" where the true theoretical limit must reside, providing a concrete target for compression efficiency.
Implications for Image Compression
A primary contribution of this work is the application of these bounds to natural image datasets, such as the Kodak benchmark. By calculating the empirical upper bound for natural images, the authors can compare theoretical limits against the performance of state-of-the-art (SOTA) neural and classical codecs.
The results on the Kodak dataset are striking: the empirical upper bounds indicate that there is at least 1 dB PSNR of theoretical room for improvement over current SOTA neural image compression methods. This suggests that despite rapid progress in deep learning-based compression, significant gains in efficiency are still possible.
Discussion and Limitations
A key insight from the study is the distinction between nominal and intrinsic dimensionality. The tightness of the lower bound depends heavily on the data's intrinsic complexity. While the bounds are remarkably tight for data with low intrinsic dimension (such as GAN-generated images), the lower bound becomes looser as the complexity of the data increases. This "curse of the lower bound" remains a challenge for high-resolution natural images, where the lower bound currently plateaus earlier than the upper bound.
Conclusion
This work provides a novel framework for empirically estimating the fundamental limits of lossy compression. By bridging the gap between $\beta$-VAEs and rate-distortion theory, the authors offer a practical tool for quantifying the optimality of compression algorithms. The finding that natural image compression still has significant room for improvement provides a clear motivation for continued research into more efficient neural architectures and entropy models.
Summary updated