A Constructive Theory of Closed-Form Rate-Distortion Functions

Dazhuan Xu, Yongming Huang, Xiaohu YouarXiv 2026 · arXiv

TL;DR

This paper introduces a "constructive" framework that simplifies the derivation of closed-form rate–distortion functions by using conditional entropy as a universal coordinate. By focusing on the posterior distribution of the test channel, the authors provide a systematic procedure to identify optimal distortion measures and solve for rate–distortion curves across a wide range of source distributions, including heavy-tailed and discrete sources.

What Problem Does This Paper Address?

In information theory, Rate–Distortion (R-D) theory tells us the minimum number of bits (the rate) needed to represent a source given a certain allowed error (the distortion). While Shannon laid the groundwork over 60 years ago, finding exact, "closed-form" mathematical solutions for specific sources remains notoriously difficult.

The challenge is that R-D functions are defined by a variational optimization problem. Traditionally, researchers had to find clever, case-specific "tricks" to match a source distribution (like a Gaussian) with a distortion measure (like squared error). Even simple cases, like a uniform source under squared error, become mathematically messy because of their finite support. There has been a lack of a unified "recipe" for identifying which distortion measures lead to solvable R-D problems and how to construct their optimal channels.

Methods

The authors propose a shift in perspective: instead of starting with a physical distortion (like MSE) and solving for the rate, they start with conditional entropy ($E$) as the primary "distortion coordinate."

Their framework, termed a posterior-based construction, follows a three-step analytic procedure:

  1. Construct a Compatible Posterior Family: They represent a test channel by its induced output distribution and a "backward" channel. They ensure "marginal compatibility"—meaning the mixture of these conditional distributions correctly recovers the original source distribution.
  2. Identify Distortion from Structure: They show that the mathematical structure of the negative log-posterior distribution naturally identifies a "candidate" fixed distortion function.
  3. Verify Optimality: Using a Gibbs representation and a "kernel mass bound," they certify that the candidate channel actually achieves the maximum possible conditional entropy for a given budget.

The paper develops two specific "construction paths":

  • The Convolution Path: Uses independent residuals (either additive or multiplicative) to ensure compatibility.
  • The Conjugate-Posterior Path: Leverages Bayesian conjugacy (where the prior and posterior belong to the same family, like Gamma-Poisson) to derive optimal joint distributions.

Datasets

As a theoretical work, this paper does not use external datasets. Instead, it evaluates the framework by deriving results for a comprehensive set of mathematical source models:

  • Continuous: Gaussian, Laplace, Gamma, Cauchy, Pareto, and Uniform.
  • Discrete: Poisson, Negative Binomial, Geometric, and Zeta sources.
  • Multivariate: Vector Gaussian and Dirichlet/Beta sources.

Key Insights and Ideas

  • Conditional Entropy as the "Common Currency": The authors demonstrate that while physical distortions (like Hamming distance or MSE) have different units, they all map to a common rate–entropy line. This allows for a unified treatment of seemingly unrelated problems.
Figure 1: Physical distortion budgets mapped to a common entropy coordinate. Distinct functions map different R-D curves to the same linear rate-entropy line.
  • Decomposing the "Rate Gap": For any sub-optimal channel, the "excess rate" (the distance from the theoretical bound) can be neatly decomposed into two parts: budget slack (not using the full distortion allowance) and posterior mismatch (how far the channel's posterior is from the ideal Gibbs form).
  • Beyond the Second Moment: Traditional R-D proofs often rely on the source having a finite second moment (variance). This framework establishes a constructive coding proof for continuous sources that only requires the log-density to be integrable, making it applicable to heavy-tailed distributions like the Cauchy distribution.

Key Results

The framework successfully recovers several classical R-D results (like Gaussian-MSE) while providing entirely new closed-form expressions:

  • Zeta Sources: The authors derived the first closed-form parametric R-D expression for Zeta sources under a "divisibility-constrained logarithmic multiplicative distortion."
  • Negative Binomial & Gamma Sources: They obtained exact expressions for Negative Binomial sources under one-sided counting distortion and Gamma sources under one-sided mean error over specific intervals.
  • Gamma-IS Recovery: The framework elegantly recovers the known (but difficult to derive) result for Gamma sources under Itakura–Saito (IS) distortion.
Figure 3: Gamma-source representations in IS-distortion and entropy-distortion coordinates.

Limitations and Future Work

While the framework is powerful, the authors note a few areas for further exploration:

  • Solvability: The "marginal mixture equations" required for compatibility are not always easy to solve analytically for every arbitrary source-distortion pair.
  • Incomplete Intervals: For some sources (like the Negative Binomial), the current decomposition only provides exact results over a specific interval of the distortion range, rather than the full curve.
  • Practical Application: The authors suggest that these theoretically-suggested distortion measures (like IS distortion for relative errors) should now be tested in practical machine learning tasks like image, video, and language compression to see if they better align with human perception or task performance.

Summary updated

Abstract

Rate-distortion functions are defined by a variational problem whose analytic solution depends on the source distribution and distortion measure. We develop a posterior-based construction framework using conditional entropy as a common distortion coordinate. Building on the rate-entropy formulation, we establish entropy-level attainability for discrete sources with finite entropy and absolutely continuous sources with integrable log densities. We give a constructive rate-entropy coding proof for finite-alphabet sources and such continuous sources, without a second-moment assumption. Marginal compatibility ensures that a candidate posterior and output distribution recover the source, while a Gibbs representation and a kernel mass bound certify attainment of maximum conditional entropy. The negative log posterior identifies candidate fixed distortions. Excess rate equals a conditional entropy gap and decomposes into budget slack and posterior mismatch. Convolution decompositions and conjugate posteriors provide two construction paths. They recover established results, including the Gamma-source rate-distortion function under Itakura-Saito distortion, and yield a closed-form parametric expression for zeta sources under divisibility-constrained logarithmic multiplicative distortion. Exact expressions are obtained on specified intervals for negative binomial sources under one-sided counting distortion and Gamma sources under one-sided mean error. A residual-count coordinate for Poisson entropy budgets and rate-entropy parametrizations of Gamma and Dirichlet counting channels connect model parameters to remaining uncertainty. The framework unifies distortion selection, compatible-channel construction, and optimality verification.
BibTeX
@misc{xu2026constructive,
  author = {Dazhuan Xu and Yongming Huang and Xiaohu You},
  title = {{A Constructive Theory of Closed-Form Rate-Distortion Functions}},
  year = {2026},
  eprint = {2611.16253},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.16253},
}
Figure