Rate-Distortion Theory: R(D) and Shannon's Lossy Source Coding Theorem

Intuition Beginner

Lossless compression preserves every bit of the original. But sometimes you can tolerate small errors. A photo stored as JPEG loses some detail. A song in MP3 drops some frequencies. The file gets much smaller, and the result is good enough.

Rate-distortion theory answers a precise question: what is the minimum number of bits per symbol needed to reproduce a source to within a given quality level? The "quality level" is measured by a distortion function that penalises errors between the original and the reproduction.

Think of it this way. You have a sequence of coin flips. You want to describe them using fewer bits than the entropy allows, which means some errors are inevitable. The rate-distortion function R(D) tells you the minimum compression rate (bits per symbol) you can achieve if you allow at most D errors per symbol on average. When D = 0, you get back the entropy H(X): perfect reproduction requires the full entropy rate. As D increases, R(D) decreases: allowing more errors lets you compress more.

For a fair coin with Hamming distortion (each wrong guess costs 1, correct costs 0), the rate-distortion function is $R(D)=1-H_b(D)$ where $H_b(D)=-D{\log }_{2}D-(1-D){\log }_2(1-D)$. At D = 0 (no errors), R = 1 bit, which is the entropy. At D = 0.5 (half the bits wrong, no better than guessing), R = 0 bits: you do not need to send anything because the decoder can guess randomly.

Shannon proved that R(D) is the fundamental limit. No code can achieve rate below R(D) with distortion at most D, and codes exist that achieve rate arbitrarily close to R(D) with distortion at most D.

Visual Beginner

Source	Distortion measure	R(D) formula	Key values
Bernoulli(1/2)	Hamming $d(x,\hat{x})=1[x\ne \hat{x}]$	$1-H_b(D)$	R(0)=1, R(1/4)=0.189, R(1/2)=0
Gaussian $\mathcal{N}(0,{\sigma }^2)$	Squared error $(x-\hat{x}{)}^2$	$\frac{1}{2}{\log }_2({\sigma }^2/D)$	R(0)=$\infty$, R(${\sigma }^2$)=0
Uniform [0,1]	Squared error	$\max (0,\frac{1}{2}{\log }_2(1/12D))$	R(0)=$\infty$, R(1/12)=0

Figure: the rate-distortion curve for a Bernoulli(1/2) source. The horizontal axis is distortion D from 0 to 0.5. The vertical axis is rate R from 0 to 1. The curve starts at (0, 1) and curves convexly down to (0.5, 0). The area above the curve is achievable; the area below is impossible.

Worked example Beginner

A fair coin produces a sequence of bits. We want to compress the sequence, allowing at most 10% of the bits to be wrong. What is the minimum rate?

Step 1. The source is Bernoulli(1/2) with Hamming distortion. The rate-distortion function is $R(D)=1-H_b(D)$.

Step 2. At D = 0.1: $H_b(0.1)=-0.1{\log }_{2}0.1-0.9{\log }_{2}0.9=0.332+0.137=0.469$ bits.

Step 3. $R(0.1)=1-0.469=0.531$ bits per symbol.

What this means: instead of needing 1 bit per symbol for perfect reproduction, you only need about 0.53 bits per symbol if you can tolerate 10% errors. For a file of 1000 bits, you can compress it to about 531 bits and the decoder will reproduce at least 900 of them correctly.

Check your understanding Beginner

Formal definition Intermediate+

Let $X$ be a random variable taking values in a finite alphabet $\mathcal{X}$ with distribution $p(x)$. Let $\hat{\mathcal{X}}$ be a reproduction alphabet and $d:\mathcal{X}\times \hat{\mathcal{X}}\to [0,\infty )$ a distortion measure.

Definition (Rate-distortion function). The rate-distortion function is:

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

where the minimisation is over all conditional distributions $p(\hat{x}|x)$ (called test channels) such that the expected distortion $\mathbb{E}[d(X,\hat{X})]={\sum }_{x,\hat{x}}p(x)p(\hat{x}|x)d(x,\hat{x})\le D$.

Definition (Rate-distortion region). The rate-distortion region is the set $\{(R,D):R\ge R(D)\}$ of achievable rate-distortion pairs.

Properties of $R(D)$:

1. Convexity: $R(D)$ is convex in $D$. If $R(D_1)$ and $R(D_2)$ are achievable, then so is $\lambda R(D_1)+(1-\lambda )R(D_2)$ at distortion $\lambda D_1+(1-\lambda )D_2$.

2. Monotonicity: $R(D)$ is non-increasing in $D$.

3. Boundary values: $R(0)=H(X)$ for lossless coding (when $d(x,\hat{x})=0$ iff $x=\hat{x}$). $R(D_{\max })=0$ where $D_{\max }={\min }_{\hat{x}}\mathbb{E}[d(X,\hat{x})]$ is the distortion achieved by guessing without any information.

The convex duality structure

The rate-distortion function has a Lagrangian dual formulation that connects to convex optimisation 44.02.01:

$$R(D)=\underset{s\le 0}{\max }\underset{p(\hat{x}|x)}{\min }[I(X;\hat{X})-s(D-\mathbb{E}[d(X,\hat{X})])].$$

The parameter $s$ is a Lagrange multiplier controlling the distortion constraint. By strong duality (guaranteed by convexity), the primal and dual formulations are equal. The optimal test channel has the Gibbs form:

$$p^{\ast }(\hat{x}|x)=\frac{q(\hat{x})e^{s\cdot d(x,\hat{x})}}{{\sum }_{{\hat{x}}^{\prime }}q({\hat{x}}^{\prime })e^{s\cdot d(x,{\hat{x}}^{\prime })}},$$

where $q(\hat{x})$ is the optimal output distribution. This structure is the foundation of the Blahut-Arimoto algorithm 46.04.04.

Key theorem with proof Intermediate+

Theorem (Shannon's lossy source coding theorem). Let $X_1,X_2,\dots$ be i.i.d. draws from $p(x)$ with distortion measure $d$. A rate $R$ is achievable with distortion $D$ if and only if $R\ge R(D)$.

More precisely:

(Achievability) For any $R>R(D)$, there exists a sequence of codes $(f_n,g_n)$ with $f_n:{\mathcal{X}}^n\to \{1,\dots ,2^{nR}\}$ and $g_n:\{1,\dots ,2^{nR}\}\to {\hat{\mathcal{X}}}^n$ such that $\frac{1}{n}\mathbb{E}[d(X^n,g_n(f_n(X^n)))]\le D+ϵ$ for all sufficiently large $n$.

(Converse) For any sequence of codes with $\frac{1}{n}\mathbb{E}[d(X^n,{\hat{X}}^n)]\le D$, the rate satisfies $R\ge R(D)$.

Proof of converse. Let $(f_n,g_n)$ be any code with rate $R$ and $\frac{1}{n}\mathbb{E}[d(X^n,{\hat{X}}^n)]\le D$. By the data-processing inequality:

$$nR\ge H(f_n(X^n))\ge H(f_n(X^n))-H(f_n(X^n)|X^n)=I(X^n;f_n(X^n))\ge I(X^n;{\hat{X}}^n).$$

Since the source is i.i.d.:

$$I(X^n;{\hat{X}}^n)\ge \sum _{i=1}^{n}I(X_i;{\hat{X}}_i)\ge \sum _{i=1}^{n}R(\mathbb{E}[d(X_i,{\hat{X}}_i)])\ge n\cdot R\left(\frac{1}{n}\sum _i\mathbb{E}[d(X_i,{\hat{X}}_i)]\right)=nR(D),$$

where the first inequality uses the fact that conditioning reduces entropy, the second uses the definition of $R(D)$ for each symbol, and the third uses convexity of $R(D)$. Dividing by $n$ gives $R\ge R(D)$. $\square$

Bridge. The rate-distortion function builds toward the Gaussian channel capacity in 46.03.05 because the Gaussian R(D) formula $\frac{1}{2}\log ({\sigma }^2/D)$ is the source-coding dual of the channel capacity $\frac{1}{2}\log (1+P/N)$; this is exactly the information-theoretic duality between source and channel coding; the foundational reason R(D) is convex is the convexity of mutual information in the conditional distribution, which generalises to the convex optimisation framework of 44.02.01; the central insight is that lossy compression is governed by the same mutual-information minimisation that governs hypothesis testing in 46.04.01, and putting these together reveals the rate-distortion function as the lossy counterpart of the entropy H(X) in lossless coding.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib has no formalisation of the rate-distortion function, distortion measures, or the mutual information minimisation problem. The optimisation is over conditional distributions $p(\hat{x}|x)$ subject to an inequality constraint, which requires Lagrangian duality over measure spaces. The achievability proof for Shannon's theorem requires a random coding argument with joint typicality, which Mathlib's probability library does not support in the required generality. The convexity of $R(D)$ and the Gibbs-form optimal test channel are unformalised. The Gaussian case requires the maximum-entropy property of Gaussians and the entropy power inequality, which are not available. This unit ships without a lean_module.

Advanced results Master

The Shannon lower bound

For any source with distortion measure $d$, the Shannon lower bound provides an easily computable lower bound on $R(D)$:

$$R(D)\ge H(X)-\underset{\lambda \ge 0}{\max }[\lambda D+\mathbb{E}[\log \sum _{\hat{x}}{e}^{-\lambda d(X,\hat{x})}]].$$

For difference distortion measures $d(x,\hat{x})=\rho (x-\hat{x})$ on continuous sources, the Shannon lower bound simplifies to:

$$R(D)\ge h(X)-\underset{\lambda :\int \rho (z)f_{\lambda }(z)dz=D}{\max }h(f_{\lambda }),$$

where $f_{\lambda }(z)\propto e^{-\lambda \rho (z)}$ is the Gibbs density. For squared-error distortion, the Gibbs density is Gaussian, and the bound is tight: $R(D)=h(X)-\frac{1}{2}\log (2\pi eD)$, which equals $\frac{1}{2}\log ({\sigma }^2/D)$ when $X$ is $\mathcal{N}(0,{\sigma }^2)$.

Vector rate-distortion and the water-filling principle

For a vector source $\mathbf{X}=(X_1,\dots ,X_k)$ with independent Gaussian components of variances ${\sigma }_1^2\ge {\sigma }_2^2\ge \cdots \ge {\sigma }_k^2$ and total squared-error distortion $D$, the rate-distortion function exhibits a water-filling structure:

$$R(D)=\sum _{i=1}^k\max \left(0,\frac{1}{2}{\log }_2\frac{{\sigma }_i^2}{\theta }\right),$$

where $\theta$ is the "water level" chosen so that ${\sum }_{i=1}^k\min (\theta ,{\sigma }_i^2)=D$. Components with variance below $\theta$ receive no rate (they are quantised to zero); components above $\theta$ receive rate proportional to the log of their variance ratio. This is the source-coding dual of the water-filling in parallel Gaussian channels 46.03.05.

The rate-distortion function and large deviations

The rate-distortion function connects to large deviations through the following observation. The probability that a randomly chosen code at rate $R$ achieves distortion less than $D$ is exponentially small in $n$, with the exponent given by $R-R(D)$ when $R>R(D)$. This is the source-coding analogue of the random coding exponent in channel coding. The error exponent for lossy source coding is:

$$E(R)=\underset{D:R(D)\le R}{\min }[R-R(D)],$$

which is positive for all $R>R(D)$ and goes to zero as $R\to R(D)$. This parallels the reliability function of channel coding 46.03.04.

Synthesis. The rate-distortion function $R(D)=\min I(X;\hat{X})$ is the lossy compression analogue of the entropy $H(X)$; it builds toward the Gaussian channel capacity where the same $\frac{1}{2}\log$ formula appears in the dual role; the central insight is that the convex duality structure connects $R(D)$ to Lagrangian optimisation 44.02.01, and this generalises to the Blahut-Arimoto computation in 46.04.04; the foundational reason the converse holds is the data-processing inequality applied to the encoder-decoder chain, putting these together we see that rate-distortion, hypothesis testing, and channel capacity are three facets of the same mutual-information landscape.

Full proof set Master

Proposition (Bernoulli R(D) achieves $D_{\max }=1/2$). For a Bernoulli(1/2) source with Hamming distortion, $D_{\max }=1/2$ and $R(D)=0$ for all $D\ge 1/2$.

Proof. $D_{\max }={\min }_{\hat{x}}\mathbb{E}[1[X\ne \hat{x}]]$. For $\hat{x}=0$: $\mathbb{E}[1[X\ne 0]]=\mathrm{Pr}[X=1]=1/2$. For $\hat{x}=1$: same by symmetry. So $D_{\max }=1/2$.

For $D\ge 1/2$, the test channel $\hat{X}\perp X$ (output independent of input) with $\hat{X}$ uniform achieves $\mathbb{E}[1[X\ne \hat{X}]]=1/2\le D$ and $I(X;\hat{X})=0$. Hence $R(D)=0$. $\square$

Proposition (Gaussian R(D) at $D={\sigma }^2$). For a Gaussian source $\mathcal{N}(0,{\sigma }^2)$ with squared-error distortion, $R({\sigma }^2)=0$.

Proof. The constant estimator $\hat{X}=0$ achieves $\mathbb{E}[(X-0{)}^2]={\sigma }^2$, so $D_{\max }={\sigma }^2$. The mutual information $I(X;\hat{X})=I(X;0)=0$ since $\hat{X}$ is deterministic. Therefore $R({\sigma }^2)=0$.

For any $D\ge {\sigma }^2$, the same estimator works, giving $R(D)=0$. The rate-distortion function has a "knee" at $D={\sigma }^2$ where it reaches zero. $\square$

Proposition (Achievability of Shannon's theorem, sketch). For any $R>R(D)$, there exists a code at rate $R$ with distortion at most $D+ϵ$.

Proof sketch. Generate a random codebook $\mathcal{C}=\{{\hat{X}}^n(1),\dots ,{\hat{X}}^n(2^{nR})\}$ by drawing each codeword independently from the output distribution $q(\hat{x}{)}^n$ induced by the optimal test channel $p^{\ast }(\hat{x}|x)$. For a given source sequence $x^n$, the encoder finds the codeword with minimum distortion: $f(x^n)=\arg {\min }_j\frac{1}{n}d(x^n,{\hat{X}}^n(j))$.

The distortion of this scheme is bounded by showing that with high probability, at least one codeword is jointly typical with $x^n$ (in the joint distribution $p(x)p^{\ast }(\hat{x}|x)$), and such a jointly typical pair has distortion close to $D$ by the law of large numbers. The probability that no codeword is jointly typical is exponentially small when $R>R(D)$, because the joint typicality requirement needs approximately $I(X;\hat{X})=R(D)$ bits to satisfy. $\square$

Connections Master

• 46.02.02 — Shannon's lossless source coding theorem is the special case $D=0$ of the lossy theorem; the rate-distortion function generalises the entropy.
• 44.02.01 — Lagrangian duality and convex optimisation provide the computational framework for R(D); the Gibbs-form test channel is the KKT optimality condition.
• 46.03.05 — The Gaussian channel capacity $C=\frac{1}{2}\log (1+P/N)$ is the dual of the Gaussian R(D) $=\frac{1}{2}\log ({\sigma }^2/D)$; water-filling appears in both.
• 46.04.04 — The Blahut-Arimoto algorithm computes R(D) iteratively using the I-projection and Pythagorean identity.
• 46.04.01 — Hypothesis testing and rate-distortion share the mutual information minimisation structure; Stein's lemma and the R(D) converse both rely on the data-processing inequality.

Historical & philosophical context Master

Shannon introduced rate-distortion theory in his 1959 paper "Coding Theorems for a Discrete Source with a Fidelity Criterion," published in the volume Information and Decision Processes (ed. Machol, McGraw-Hill, pp. 93-126). This paper extended the 1948 source coding theorem from lossless to lossy coding, introducing the distortion measure and the rate-distortion function. Shannon proved both the achievability (via random coding) and the converse (via the data-processing inequality), establishing the complete characterisation.

Toby Berger's 1971 monograph Rate Distortion Theory: A Mathematical Basis for Data Compression (Prentice-Hall) systematised the theory, computing R(D) for many source-distortion pairs and developing the connection to convex optimisation. Berger showed that the reverse water-filling principle for Gaussian sources extends to correlated sources via the Karhunen-Loeve transform.

The computational problem of finding R(D) was solved by Blahut (1972) and Arimoto (1972), who independently developed the iterative algorithm that bears their names. The Blahut-Arimoto algorithm alternates between computing the optimal test channel (given the output distribution) and the optimal output distribution (given the test channel), converging to R(D) from above. This algorithm is studied in 46.04.04.

Rate-distortion theory has deep connections to statistical mechanics. The Gibbs-form optimal test channel $p^{\ast }(\hat{x}|x)\propto q(\hat{x})e^{sd(x,\hat{x})}$ is analogous to the Boltzmann distribution, with the Lagrange multiplier $s$ playing the role of inverse temperature and the distortion playing the role of energy. This analogy was developed by Rose (1994) in his paper "Rate-Distortion Theory and the Vector Quantisation of Non-Compact Sources" (IEEE Trans. IT).

Bibliography Master

@incollection{shannon1959,
  author    = {Shannon, C. E.},
  title     = {Coding Theorems for a Discrete Source with a Fidelity Criterion},
  booktitle = {Information and Decision Processes},
  editor    = {Machol, R. E.},
  publisher = {McGraw-Hill},
  pages     = {93--126},
  year      = {1959},
}
@book{berger1971,
  author    = {Berger, T.},
  title     = {Rate Distortion Theory: A Mathematical Basis for Data Compression},
  publisher = {Prentice-Hall},
  year      = {1971},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}
@article{blahut1972,
  author  = {Blahut, R. E.},
  title   = {Computation of Channel Capacity and Rate-Distortion Functions},
  journal = {IEEE Transactions on Information Theory},
  volume  = {18},
  number  = {4},
  pages   = {460--473},
  year    = {1972},
}
@article{arimoto1972,
  author  = {Arimoto, S.},
  title   = {An Algorithm for Computing the Capacity of Arbitrary Discrete Memoryless Channels},
  journal = {IEEE Transactions on Information Theory},
  volume  = {18},
  number  = {1},
  pages   = {14--20},
  year    = {1972},
}