Rate-Distortion Theory

Overview & Motivation

Shannon’s source coding theorem establishes that the entropy rate $H$ is the fundamental limit of lossless compression. But lossless compression is often wildly impractical: a raw audio CD uses 1,411 kbps; MP3 achieves perceptually transparent quality at 128 kbps — a 10× reduction by accepting controlled distortion. JPEG, H.264, and every streaming codec you’ve ever used make the same bargain: trade fidelity for bits.

Rate-distortion theory answers the question that lossless coding leaves open: if we allow an average distortion of at most $D$, what is the minimum number of bits per source symbol we must transmit? The answer is the rate-distortion function $R(D)$, which Shannon proved is the solution to a convex optimization problem over conditional distributions:

$R(D) = \min_{p(\hat{x}|x):\, \mathbb{E}[d(X,\hat{X})] \leq D} I(X; \hat{X})$

This is one of the deepest results in information theory: it gives a single number that separates the possible from the impossible. Any coding scheme operating below $R(D)$ bits per symbol must incur distortion greater than $D$, no matter how clever the encoder.

What We Cover

1. Distortion measures — Hamming distortion, squared error, and the expected distortion framework
2. The rate-distortion function — definition, properties (convex, non-increasing, boundary values), and the operational meaning
3. Rate-distortion theorem — Shannon’s achievability and converse: $R(D)$ is the exact boundary between achievable and unachievable (rate, distortion) pairs
4. Closed-form solutions — binary source with Hamming distortion, Gaussian source with squared error, parametric form, Shannon lower bound
5. The Blahut–Arimoto algorithm — alternating minimization for computing $R(D)$ numerically
6. The information bottleneck — compression with relevance, connections to deep learning (VIB, $\beta$-VAE)
7. Computational notes — Python implementations, VAE loss as rate-distortion, neural compression

Prerequisites

• Shannon Entropy & Mutual Information — we use entropy, mutual information, and the source coding theorem throughout
• Convex Analysis — convexity of $R(D)$, Lagrangian duality, and the KKT conditions that yield the parametric form

---

Distortion Measures

Before we can talk about “acceptable” lossy compression, we need a formal notion of how much damage we’ve done to the source. A distortion measure quantifies the cost of reproducing source symbol $x$ as $\hat{x}$.

Two distortion measures dominate information theory: one for discrete sources, one for continuous.

Hamming distortion treats all errors equally — a single bit flip costs the same regardless of context. Squared error, by contrast, is graded: reproducing 3.0 as 3.1 costs far less than reproducing it as 10.0. The choice of distortion measure shapes the entire rate-distortion curve, because it determines what “tolerable” compression means.

For a discrete source with alphabet $\{0, 1, \ldots, k-1\}$, the Hamming distortion can be organized into a distortion matrix $\mathbf{D}$ where $D_{ij} = d(x_i, \hat{x}_j)$. For Hamming distortion, this is simply the identity complement: zeros on the diagonal, ones everywhere else.

---

The Rate-Distortion Function

The rate-distortion function answers the central question: what is the minimum number of bits per source symbol we need to transmit, if we can tolerate average distortion $\leq D$?

The test channel $p(\hat{x}|x)$ describes how we map source symbols to reproductions — it’s the probabilistic encoding rule. The mutual information $I(X; \hat{X})$ measures how many bits of information the reproduction carries about the source. Minimizing $I(X; \hat{X})$ subject to the distortion constraint finds the most compressed representation that still meets the fidelity requirement.

Properties (ii) and (iii) together tell us that $R(D)$ is a convex, non-increasing curve from $R(0) = H(X)$ down to $R(D_{\max}) = 0$. The region above the curve is achievable (we can compress to that rate at that distortion); the region below is unachievable (no coding scheme can reach it).

Source:Binary uniform (p = 0.5)Binary (p = 0.3)Binary (p = 0.1)Gaussian (σ² = 1)Gaussian (σ² = 2)Operating point D:0.150

---

The Rate-Distortion Theorem

Shannon’s rate-distortion theorem gives $R(D)$ its operational meaning: it is the exact boundary between achievable and unachievable compression.

The theorem is the operational backbone of lossy compression. The achievability proof is constructive (random coding with joint typicality), while the converse is information-theoretic (any code, no matter how clever, must respect $R(D)$).

---

Closed-Form Solutions

For two important source-distortion pairs, $R(D)$ has a clean analytical form. These serve as benchmarks and building blocks for understanding the general case.

Binary Source with Hamming Distortion

For the uniform binary source ($p = 0.5$), this simplifies to $R(D) = 1 - H_b(D)$: we start at 1 bit (lossless) and reach 0 bits at $D = 0.5$ (pure guessing).

Gaussian Source with Squared Error

The Gaussian $R(D)$ has a particularly clean interpretation: halving the distortion costs exactly one extra bit per sample. This logarithmic relationship is the foundation of quantization theory.

Parametric Form and the Shannon Lower Bound

For the binary source, the slope parameter is $s = \log_2\!\big(D/(1-D)\big)$ and the test channel is BSC($D$). For the Gaussian source, $s = -1/(2D \ln 2)$, and the test channel adds $\mathcal{N}(0, D)$ noise.

The Shannon lower bound tells us that the Gaussian source is the hardest to compress (among sources with the same variance), in the sense that it requires the most bits at every distortion level.

---

The Blahut–Arimoto Algorithm

For general discrete sources where a closed-form $R(D)$ is unavailable, the Blahut–Arimoto (BA) algorithm computes $R(D)$ via alternating minimization. The algorithm exploits the convex structure of the rate-distortion optimization.

The connection to the EM algorithm is direct: Step 1 is analogous to the E-step (computing a posterior given current parameters), and Step 2 is analogous to the M-step (updating parameters given the posterior). Both algorithms exploit the same alternating minimization structure on convex objectives.

Source:Uniform ternaryNon-uniform [0.5, 0.3, 0.2]Quaternary [0.4, 0.3, 0.2, 0.1]Slope s:-5.0

StepRunResetIteration: 0

Here is the Python implementation:

def blahut_arimoto_rd(px, distortion_matrix, slope, max_iter=200, tol=1e-10):
    """Blahut-Arimoto for one point on the R(D) curve."""
    n_x, n_xhat = distortion_matrix.shape
    q_xhat = np.ones(n_xhat) / n_xhat  # uniform initialization

    for iteration in range(max_iter):
        # Step 1: optimal test channel
        log_channel = np.log(np.maximum(q_xhat, 1e-300)) + slope * distortion_matrix
        log_channel -= log_channel.max(axis=1, keepdims=True)
        p_xhat_given_x = np.exp(log_channel)
        p_xhat_given_x /= p_xhat_given_x.sum(axis=1, keepdims=True)

        # Step 2: update output marginal
        new_q = px @ p_xhat_given_x
        new_q = np.maximum(new_q, 1e-300)

        if np.max(np.abs(new_q - q_xhat)) < tol:
            break
        q_xhat = new_q

    # Compute rate and distortion
    joint = px[:, None] * p_xhat_given_x
    rate = mutual_information(joint)
    distortion = np.sum(joint * distortion_matrix)
    return rate, distortion, q_xhat, p_xhat_given_x

---

The Information Bottleneck

The information bottleneck (IB) method, introduced by Tishby, Pereira & Bialek (1999), extends rate-distortion theory from compression of $X$ to compression of $X$ while preserving information about a relevant variable $Y$. This is the bridge between rate-distortion theory and representation learning.

The IB is not just an abstract optimization — it is a special case of rate-distortion theory with an information-theoretic distortion measure.

The IB curve tells us exactly how much relevance we must sacrifice for each bit of compression. Low $\beta$ means heavy compression (small $I(X;T)$, low relevance); high $\beta$ means preserving relevance at the cost of a more complex representation.

Joint p(x,y):Noisy identity channelSymmetric channelAsymmetric channelβ:5.0|T|:234

def information_bottleneck(p_xy, beta, n_t=4, max_iter=500, tol=1e-10):
    """Compute IB solution for given beta via alternating optimization."""
    n_x, n_y = p_xy.shape
    p_x = p_xy.sum(axis=1)
    p_y_given_x = p_xy / p_x[:, None]

    # Initialize p(t|x) randomly
    p_t_given_x = np.random.dirichlet(np.ones(n_t), size=n_x)

    for _ in range(max_iter):
        p_t = p_x @ p_t_given_x
        p_t = np.maximum(p_t, 1e-300)

        # p(y|t) from Bayes: p(y|t) = sum_x p(y|x) p(x|t)
        p_y_given_t = np.zeros((n_t, n_y))
        for t in range(n_t):
            if p_t[t] > 1e-300:
                p_y_given_t[t] = (p_t_given_x[:, t] * p_x) @ p_y_given_x / p_t[t]

        # Update p(t|x) proportional to p(t) exp(-beta * D_KL(p(y|x) || p(y|t)))
        new_p = np.zeros_like(p_t_given_x)
        for i in range(n_x):
            for t in range(n_t):
                dkl = np.sum(
                    p_y_given_x[i] * np.log(
                        np.maximum(p_y_given_x[i], 1e-300)
                        / np.maximum(p_y_given_t[t], 1e-300)
                    ) * (p_y_given_x[i] > 0)
                )
                new_p[i, t] = p_t[t] * np.exp(-beta * dkl)
            new_p[i] /= np.maximum(new_p[i].sum(), 1e-300)

        if np.max(np.abs(new_p - p_t_given_x)) < tol:
            break
        p_t_given_x = new_p

    # Compute I(X;T) and I(T;Y)
    p_xt = p_x[:, None] * p_t_given_x
    I_XT = mutual_information(p_xt)
    p_ty = np.diag(p_t) @ p_y_given_t
    I_TY = mutual_information(p_ty)
    return I_XT, I_TY

Data Processing and Successive Refinement

Two additional results connect rate-distortion theory to practical coding systems.

Successive refinement is the theoretical foundation of progressive coding (JPEG progressive, scalable video coding): a base layer provides coarse quality, and enhancement layers refine it without wasting bits.

---

Computational Notes

Rate-distortion theory connects directly to modern ML through three bridges: the VAE loss, neural compression, and the information bottleneck in deep learning.

VAE Loss as Rate-Distortion

β:1.00σ²:0.5124

Python Implementations

Here are reference implementations for computing rate-distortion functions:

def rate_distortion_binary(p, D):
    """R(D) = H_b(p) - H_b(D) for binary source with Hamming distortion."""
    D_max = min(p, 1 - p)
    if D >= D_max:
        return 0.0
    return H_b(p) - H_b(D)

def rate_distortion_gaussian(sigma2, D):
    """R(D) = 0.5 * log2(sigma2 / D) for Gaussian source."""
    if D >= sigma2:
        return 0.0
    return 0.5 * np.log2(sigma2 / D)

# VAE loss decomposition
def vae_loss(x, encoder, decoder, beta=1.0):
    """L = E[-log p(x|z)] + β D_KL(q(z|x) || p(z))"""
    mu, logvar = encoder(x)
    z = reparameterize(mu, logvar)

    # Distortion: reconstruction error
    recon_loss = -decoder.log_prob(x, z).mean()

    # Rate: KL divergence from posterior to prior
    kl_loss = -0.5 * (1 + logvar - mu**2 - logvar.exp()).sum(dim=-1).mean()

    return recon_loss + beta * kl_loss  # rate-distortion Lagrangian

Neural Compression

Modern learned image and video codecs operationalize rate-distortion theory directly. The encoder-decoder architecture learns the optimal test channel end-to-end, with the loss function being exactly the rate-distortion Lagrangian:

$\mathcal{L} = \underbrace{\mathbb{E}[\| x - \hat{x} \|^2]}_{\text{distortion}} + \lambda \underbrace{\mathbb{E}[-\log p(\hat{z})]}_{\text{rate}}$

where $\hat{z}$ is the quantized latent representation and $p(\hat{z})$ is the learned entropy model. Different $\lambda$ values trace out the operational R(D) curve of the neural codec. Frameworks like CompressAI (Ballé et al.) achieve state-of-the-art image compression by learning both the transform and the entropy model jointly.

---

Connections & Further Reading

Connection Map

• Shannon Entropy & Mutual Information — $R(D) = \min I(X; \hat{X})$: the rate-distortion function is defined as a minimization of mutual information. At $D=0$, $R(0) = H(X)$ recovers the lossless source coding limit.

• KL Divergence & f-Divergences — The KL divergence appears in the IB distortion measure $d_{IB}(x,t) = D_{\mathrm{KL}}(p(y \mid x) \| p(y \mid t))$ and in the VAE rate term $D_{\mathrm{KL}}(q(z \mid x) \| p(z))$.

• Convex Analysis — $R(D)$ is convex in $D$: the rate-distortion optimization is a convex program. The Blahut–Arimoto algorithm exploits this structure via alternating minimization.

• Lagrangian Duality & KKT — The slope $s$ in the parametric form of $R(D)$ is the Lagrange multiplier for the distortion constraint. Strong duality holds because the optimization is convex.

• Minimum Description Length — MDL connects source coding (Shannon) to model selection: the best model minimizes description length = code length + model complexity.

Notation Reference

Symbol	Meaning
$d(x, \hat{x})$	Distortion function: cost of reproducing $x$ as $\hat{x}$
$D = \mathbb{E}[d(X, \hat{X})]$	Expected (average) distortion
$R(D)$	Rate-distortion function: minimum bits/symbol at distortion $\leq D$
$p(\hat{x} \mid x)$	Test channel: conditional distribution from source to reproduction
$D_{\max}$	Maximum useful distortion: achievable without any communication
$s$	Slope parameter (Lagrange multiplier) in the parametric form
$\beta$	Trade-off parameter in IB / $\beta$-VAE
$I(X; T)$	Complexity (compression) in the information bottleneck
$I(T; Y)$	Relevance (preserved information) in the information bottleneck