Contents / Information Theory / Rate–Distortion Theory

Chapter 10

Rate–Distortion Theory

The best rate achievable at a given distortion, computed in closed form where it can be and numerically where it cannot.

Introduction

The best rate achievable at a given distortion, computed in closed form where it can be and numerically where it cannot.

10.1The Lossy Compression Problem

Fix a source alphabet $X$ and a reproduction alphabet $\hat{X}$ . The two need not be the same set, and it is worth keeping them notationally distinct: a 16-bit audio sample lives in a set of size $65536$ , while its reproduction may be one of $256$ levels, or one of a continuum.

Definition 10.1 (Distortion measure). A distortion measure is a map

d : X \times \hat{X} \to [0, \infty) .

It is bounded if $d_{m a x} = sup_{x, \overset{x}{^}} d (x, \overset{x}{^}) < \infty$ . The distortion between sequences is the single-letter (per-symbol average) extension

d (x^{n}, \overset{x}{^}^{n}) = \frac{1}{n} i = 1 \sum n d (x_{i}, \overset{x}{^}_{i}) .

Two measures do almost all the work in practice and in this chapter. Hamming distortion on a common finite alphabet, $d (x, \overset{x}{^}) = 1 [x \neq = \overset{x}{^}]$ , makes $E [d]$ the symbol error probability. Squared-error distortion on $R$ , $d (x, \overset{x}{^}) = (x - \overset{x}{^})^{2}$ , makes $E [d]$ the mean squared error. Squared error is unbounded, which costs some technical work in the proofs but changes none of the answers.

Notation (Blocks, codes, rates). An $(n, 2^{n R})$ rate–distortion code consists of an encoder

f_{n} : X^{n} \to {1, 2, \dots, 2^{n R}}

and a decoder $g_{n} : {1, \dots, 2^{n R}} \to \hat{X}^{n}$ . Its rate is $R$ bits per source symbol, and its distortion is

D (f_{n}, g_{n}) = E [d (X^{n}, g_{n} (f_{n} (X^{n})))],

the expectation taken over the source. The set $C = g_{n} ({1, \dots, 2^{n R}})$ of reproduction sequences is the codebook; the encoder chooses a codeword, the decoder is merely a lookup table.

Definition 10.2 (Operational rate–distortion function). A pair $(R, D)$ is achievable if there is a sequence of $(n, 2^{n R})$ codes with

n \to \infty lim sup D (f_{n}, g_{n}) \leq D .

The operational rate–distortion function $R^{(o)} (D)$ is the infimum of all rates $R$ such that $(R, D)$ is achievable.

Everything in this chapter is an attempt to replace that infimum-over-codes, which you cannot compute, with a formula in the source distribution, which you can.

Intuition. If you insist on a perfect reproduction you must pay the full price of the source's randomness. If you allow the reconstructed picture to look a little blurry, you can describe it with far fewer bits — and $R (D)$ is the exact exchange rate between blur and bits.

The curve is the boundary of the achievable region: everything above and to the right of it can be done, everything below and to the left cannot, no matter how clever the codec.

Two endpoints of the curve are forced by the definitions, and it is worth naming them before doing any work.

Definition 10.3 (Minimum and maximum distortion).

D_{m i n} = E [\overset{x}{^} \in \hat{X} min d (X, \overset{x}{^})], D_{m a x} = \overset{x}{^} \in \hat{X} min E [d (X, \overset{x}{^})] .

$D_{m i n}$ is the distortion of a decoder that is told $X$ exactly; $D_{m a x}$ is the distortion of the best decoder that is told nothing.

The order of the minimum and the expectation is the whole content of that definition. For Hamming distortion $D_{m i n} = 0$ and $D_{m a x} = 1 - max_{x} p (x)$ , the error probability of always guessing the most likely symbol. For squared error with $\hat{X} = R$ , $D_{m i n} = 0$ and $D_{m a x} = Var (X)$ , attained by the constant reproduction $\overset{x}{^} = E [X]$ .

Example 10.4 (Reading the two endpoints off a source). Let $X$ take values in ${a, b, c}$ with probabilities $0.7, 0.2, 0.1$ under Hamming distortion, and let $W \sim N (3, 4)$ under squared error. Find $D_{m i n}$ and $D_{m a x}$ for each.

Solution. For $X$ : every symbol has a perfect reproduction available, so $min_{\overset{x}{^}} d (x, \overset{x}{^}) = 0$ for each $x$ and $D_{m i n} = 0$ . For the other endpoint, a rate- $0$ decoder must output a fixed symbol; outputting $a$ errs with probability $0.3$ , outputting $b$ with probability $0.8$ , outputting $c$ with probability $0.9$ . Hence $D_{m a x} = 0.3$ .

For $W$ : again $D_{m i n} = 0$ . A constant reproduction $c$ has $E [(W - c)^{2}] = Var (W) + (E [W] - c)^{2}$ , minimized at $c = 3$ , so $D_{m a x} = 4$ .

Sanity check: in both cases $D_{m a x}$ is the distortion at rate $0$ and $D_{m i n}$ the distortion at infinite rate, so the interesting part of the curve lives on $[0, 0.3]$ and $[0, 4]$ respectively. Outside that interval $R (D)$ is either undefined (below $D_{m i n}$ ) or identically zero (above $D_{m a x}$ ).□

Pitfall. $D_{m a x}$ is not the largest value the distortion measure can take. For squared error on a Gaussian source the distortion of a bad reproduction is unbounded, yet $D_{m a x} = σ^{2}$ , because $D_{m a x}$ is defined by the best zero-rate reproduction, not the worst one.

Exercises for §10.1 →

10.2The Information Rate–Distortion Function

The operational definition quantifies over all codes of all block lengths. The informational one quantifies over a compact set of conditional distributions on a single symbol, and is the object we can actually compute with.

Definition 10.5 (Information rate–distortion function). For a source $X \sim p (x)$ and distortion measure $d$ , the information rate–distortion function is

R^{(I)} (D) = p (\overset{x}{^} ∣ x) : E [d (X, \hat{X})] \leq D min I (X; \hat{X}),

the minimum taken over all conditional distributions — test channels — for which the joint law $p (x) p (\overset{x}{^} ∣ x)$ meets the distortion budget. The feasible set is empty, and $R^{(I)} (D) = \infty$ , when $D < D_{m i n}$ .

Notation (Test channel). The conditional law $p (\overset{x}{^} ∣ x)$ is called a test channel because it is formally a channel from $X$ to $\hat{X}$ . It is not a physical channel and nothing is transmitted through it: it is a bookkeeping device that encodes a proposed statistical relationship between source and reproduction, and $I (X; \hat{X})$ scores that relationship.

Writing " $min$ " rather than " $in f$ " needs a word of justification on a finite alphabet.

Proposition 10.6 (The minimum is attained). If $X$ and $\hat{X}$ are finite and $D \geq D_{m i n}$ , the minimum defining $R^{(I)} (D)$ is attained by some test channel.

Proof. The set of conditional distributions $p (\overset{x}{^} ∣ x)$ is a product of probability simplices, hence a compact subset of $R^{∣ X ∣∣ \hat{X} ∣}$ . The expected distortion is a linear, hence continuous, function of $p (\overset{x}{^} ∣ x)$ , so the feasible set ${p (\overset{x}{^} ∣ x) : E [d] \leq D}$ is a closed subset of a compact set, hence compact; it is nonempty because $D \geq D_{m i n}$ lets each $x$ put all its mass on an $\overset{x}{^}$ achieving $min_{\overset{x}{^}} d (x, \overset{x}{^})$ . Finally $I (X; \hat{X})$ is continuous in $p (\overset{x}{^} ∣ x)$ for fixed $p (x)$ , with the convention $0 lo g 0 = 0$ . A continuous function on a nonempty compact set attains its minimum.∎

For continuous alphabets the minimum may only be an infimum, and the mutual information is the general measure-theoretic one; every formula below survives, and in the Gaussian case the infimum is attained.

Intuition. $R^{(I)} (D)$ asks: how little can the reproduction know about the source, while still resembling it?

Mutual information is the right currency because it is exactly the number of bits a description must carry — this is what the rate–distortion theorem will make precise. So we choose the statistical relationship between $X$ and $\hat{X}$ first, and only afterwards worry about codes that realize it.

Example 10.7 (A binary source, computed from the backward channel). Let $X \sim Bernoulli (1/2)$ on ${0, 1}$ with Hamming distortion. Compute $R^{(I)} (D)$ for $0 \leq D \leq 1/2$ .

Solution. Lower bound. For any test channel with $Pr [X \neq = \hat{X}] \leq D$ ,

I (X; \hat{X}) = H (X) - H (X ∣ \hat{X}) = 1 - H (X \oplus \hat{X} ∣ \hat{X}) \geq 1 - H (X \oplus \hat{X}) \geq 1 - h_{2} (D),

where the first inequality is "conditioning reduces entropy" and the second uses $Pr [X \oplus \hat{X} = 1] \leq D \leq 1/2$ together with the fact that $h_{2}$ is increasing on $[0, 1/2]$ . Here $h_{2} (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t)$ .

Upper bound. Specify the backward channel instead: let $\hat{X} \sim Bernoulli (1/2)$ and $X = \hat{X} \oplus Z$ with $Z \sim Bernoulli (D)$ independent of $\hat{X}$ . Then $X$ is indeed $Bernoulli (1/2)$ as required, $Pr [X \neq = \hat{X}] = D$ , and $I (X; \hat{X}) = H (X) - H (X ∣ \hat{X}) = 1 - h_{2} (D)$ . This exhibits a feasible test channel meeting the lower bound.

Hence $R^{(I)} (D) = 1 - h_{2} (D)$ for $0 \leq D \leq 1/2$ , and $R^{(I)} (D) = 0$ for $D \geq 1/2 = D_{m a x}$ .

Sanity check: at $D = 0$ we get $1$ bit, the entropy of a fair bit; at $D = 1/2$ we get $0$ , and indeed a decoder that flips its own coin agrees with $X$ half the time for free.□

Remark. The manoeuvre in that solution — specify the backward channel $p (x ∣ \overset{x}{^})$ , not the forward one — is the standard trick for producing optimal test channels, and it recurs for the Gaussian source below. It works because the lower bound is naturally written in terms of $H (X ∣ \hat{X})$ , so the backward description makes the bound tight by construction. The one thing that must then be checked is consistency: the backward channel together with the chosen marginal on $\hat{X}$ must reproduce the given source law $p (x)$ .

Exercises for §10.2 →

10.3Properties of the Rate–Distortion Function

Before computing $R^{(I)}$ for particular sources it pays to establish its shape, because those properties are what make the converse proof work and what justify the numerical algorithms.

Lemma 10.8 (Mutual information is convex in the test channel). For a fixed source distribution $p (x)$ , the map $p (\overset{x}{^} ∣ x) \mapsto I (X; \hat{X})$ is convex.

Proof. Write the mutual information as a minimum of a conditional relative entropy:

I (X; \hat{X}) = r min x \sum p (x) D (p (\cdot ∣ x) r),

the minimum over all distributions $r$ on $\hat{X}$ . The identity holds because $\sum_{x} p (x) D (p (\cdot ∣ x) ∥ r) = I (X; \hat{X}) + D (p_{\hat{X}} ∥ r) \geq I (X; \hat{X})$ , with equality exactly at $r = p_{\hat{X}}$ . Now $F (p (\cdot ∣ \cdot), r) = \sum_{x} p (x) D (p (\cdot ∣ x) ∥ r)$ is jointly convex in its two arguments, since relative entropy is jointly convex in its pair of arguments and a nonnegative weighted sum of jointly convex functions is jointly convex. Partial minimization of a jointly convex function over one argument leaves a convex function of the other.∎

Theorem 10.9 (Shape of the rate–distortion curve). On $[D_{m i n}, \infty)$ the function $R^{(I)} (D)$ is

non-negative and non-increasing;
convex;
continuous on $(D_{m i n}, \infty)$ , and strictly decreasing wherever it is positive;
equal to $0$ for every $D \geq D_{m a x}$ , and strictly positive for $D_{m i n} \leq D < D_{m a x}$ .

Proof. (1) Mutual information is non-negative, and enlarging $D$ enlarges the feasible set, so the minimum cannot increase.

(2) Let $p_{1}$ and $p_{2}$ be test channels attaining $R^{(I)} (D_{1})$ and $R^{(I)} (D_{2})$ , and let $p_{λ} = λ p_{1} + (1 - λ) p_{2}$ for $λ \in [0, 1]$ . Expected distortion is linear in the test channel, so $p_{λ}$ has distortion $λ D_{1} + (1 - λ) D_{2}$ and is feasible for that budget. By the previous lemma,

R^{(I)} (λ D_{1} + (1 - λ) D_{2}) \leq I_{p_{λ}} (X; \hat{X}) \leq λ I_{p_{1}} (X; \hat{X}) + (1 - λ) I_{p_{2}} (X; \hat{X}),

and the right-hand side is $λ R^{(I)} (D_{1}) + (1 - λ) R^{(I)} (D_{2})$ .

(3) A finite convex function on an interval is continuous on its interior. For strict decrease, suppose $R^{(I)} (D) = R^{(I)} (D^{'}) = c > 0$ with $D < D^{'}$ . Convexity plus monotonicity would force $R^{(I)}$ to be constant at $c$ on all of $[D, D_{m a x}]$ , contradicting $R^{(I)} (D_{m a x}) = 0 < c$ , which is part (4).

(4) If $D \geq D_{m a x}$ , take $\hat{X}$ to be the constant $\overset{x}{^}^{*}$ attaining $min_{\overset{x}{^}} E [d (X, \overset{x}{^})]$ ; it is feasible and independent of $X$ , so $I = 0$ . Conversely $I (X; \hat{X}) = 0$ forces $\hat{X}$ independent of $X$ , and then $E [d (X, \hat{X})] = \sum_{\overset{x}{^}} p (\overset{x}{^}) E [d (X, \overset{x}{^})] \geq D_{m a x}$ ; so a distortion strictly below $D_{m a x}$ forces a strictly positive rate.∎

Property (2) is the workhorse. It is what lets the converse proof push a per-symbol average through Jensen's inequality, and it is why the parametric sweep of the next part traces the whole curve rather than only part of it.

Now the endpoint at $D = D_{m i n}$ , which is where the classical link to lossless coding lives — and where a widely repeated statement needs care.

Proposition 10.10 (The value at zero distortion). Suppose $X = \hat{X}$ is discrete and $d$ satisfies $d (x, \overset{x}{^}) = 0$ if and only if $x = \overset{x}{^}$ . Then $D_{m i n} = 0$ and

R^{(I)} (0) = H (X) .

If instead $X$ is a continuous random variable under squared-error distortion with $h (X) > - \infty$ , then $R^{(I)} (D) \to \infty$ as $D ↓ 0$ ; in particular $R^{(I)} (0)$ is not the differential entropy $h (X)$ , and is not finite at all.

Proof. Discrete case. Feasibility at $D = 0$ forces $E [d (X, \hat{X})] = 0$ , and since $d \geq 0$ with equality only on the diagonal, $Pr [\hat{X} \neq = X] = 0$ . Then $H (X ∣ \hat{X}) = 0$ and $I (X; \hat{X}) = H (X) - H (X ∣ \hat{X}) = H (X)$ . Every feasible channel gives the same value, so the minimum is $H (X)$ .

Continuous case. By the Shannon lower bound proved later in this chapter, $R^{(I)} (D) \geq h (X) - \frac{1}{2} lo g_{2} (2 π eD)$ for squared-error distortion. As $D ↓ 0$ the subtracted term tends to $- \infty$ , so the bound tends to $+ \infty$ .∎

Pitfall. The slogan " $R (0) = H (X)$ " is a theorem about discrete sources only, and even there it needs $d$ to vanish only on the diagonal. Replacing $H (X)$ by the differential entropy $h (X)$ for a continuous source is simply false: $h (X)$ is finite and may be negative — a $N (0, σ^{2})$ with $σ^{2} < 1/ (2 π e)$ has $h (X) < 0$ — whereas the rate needed to describe a real number exactly is infinite. What is true for a continuous source is the high-rate statement $R (D) \approx h (X) - \frac{1}{2} lo g_{2} (2 π eD)$ , in which the differential entropy appears only as an additive offset alongside a term that blows up.

Corollary 10.11 (Lossless coding is the $D = 0$ corner). For a discrete memoryless source with a distortion measure vanishing only on the diagonal, the rate–distortion theorem at $D = 0$ reduces to the source coding theorem: the minimum rate for asymptotically error-free description is $H (X)$ .

Example 10.12 (A three-point source: endpoints and one interior value). Let $X \in {a, b, c}$ with $p = (0.5, 0.3, 0.2)$ under Hamming distortion. Give $R (0)$ and $D_{m a x}$ , and produce a feasible rate at $D = 0.2$ .

Solution. $R (0) = H (X) = - 0.5 lo g_{2} 0.5 - 0.3 lo g_{2} 0.3 - 0.2 lo g_{2} 0.2 = 0.5 + 0.5211 + 0.4644 = 1.4855$ bits.

$D_{m a x} = 1 - max_{x} p (x) = 1 - 0.5 = 0.5$ , attained by always reproducing $a$ .

At $D = 0.2$ , take the deterministic test channel $a \mapsto a$ , $b \mapsto b$ , $c \mapsto a$ . Its distortion is $Pr [X = c] = 0.2$ , so it is feasible, and $\hat{X}$ is then binary with $Pr [\hat{X} = a] = 0.7$ . Since $\hat{X}$ is a deterministic function of $X$ , $I (X; \hat{X}) = H (\hat{X}) - H (\hat{X} ∣ X) = h_{2} (0.3) - 0 = 0.8813$ bits.

So $R (0.2) \leq 0.8813$ . Sanity check: this sits strictly between $0$ (the value at $D_{m a x} = 0.5$ ) and $1.4855$ (the value at $D = 0$ ), as monotonicity demands. It is only an upper bound — a randomized test channel does better, and the exact value must be found numerically by the Blahut–Arimoto algorithm of the next part.□

Exercises for §10.3 →

10.4The Bernoulli and Gaussian Rate–Distortion Functions

Two sources admit clean closed forms, and between them they carry most of the intuition in the subject.

Theorem 10.13 (Bernoulli source under Hamming distortion). Let $X \sim Bernoulli (p)$ with $p \leq 1/2$ , and let $d$ be Hamming distortion on ${0, 1}$ . Then

R (D) = {h_{2} (p) - h_{2} (D), 0, 0 \leq D \leq p, D > p .

Proof. Converse (lower bound). Let $p (\overset{x}{^} ∣ x)$ be any test channel with $Pr [X \neq = \hat{X}] \leq D \leq p$ , and put $Z = X \oplus \hat{X}$ , so $Pr [Z = 1] \leq D$ . Then

I (X; \hat{X}) = H (X) - H (X ∣ \hat{X}) = h_{2} (p) - H (X \oplus \hat{X} ∣ \hat{X}) \geq h_{2} (p) - H (Z) \geq h_{2} (p) - h_{2} (D),

using $H (X ∣ \hat{X}) = H (X \oplus \hat{X} ∣ \hat{X})$ — given $\hat{X}$ , knowing $X$ and knowing $X \oplus \hat{X}$ are the same knowledge — then conditioning reduces entropy, then monotonicity of $h_{2}$ on $[0, 1/2]$ with $Pr [Z = 1] \leq D \leq p \leq 1/2$ .

Achievability (upper bound). Specify the backward channel. Let $\hat{X} \sim Bernoulli (r)$ with

r = \frac{p - D}{1 - 2 D} \in [0, 1/2] for D \leq p \leq 1/2,

and let $X = \hat{X} \oplus Z$ with $Z \sim Bernoulli (D)$ independent of $\hat{X}$ . Consistency: $Pr [X = 1] = r (1 - D) + (1 - r) D = r (1 - 2 D) + D = (p - D) + D = p$ , as required. Feasibility: $Pr [X \neq = \hat{X}] = Pr [Z = 1] = D$ . Value: $I (X; \hat{X}) = H (X) - H (X ∣ \hat{X}) = h_{2} (p) - H (Z) = h_{2} (p) - h_{2} (D)$ .

The flat part. For $D > p$ the constant reproduction $\hat{X} \equiv 0$ has distortion $Pr [X = 1] = p < D$ and $I = 0$ ; and $D_{m a x} = 1 - max (p, 1 - p) = p$ , so by the shape theorem $R (D) = 0$ exactly on $D \geq p$ .∎

Pitfall. The formula $h_{2} (p) - h_{2} (D)$ is wrong for $D > p$ : it goes negative — take $p = 0.1$ , $D = 0.3$ , giving $0.469 - 0.881 < 0$ — which is impossible for a mutual information. The restriction $D \leq min (p, 1 - p)$ is part of the theorem, not a technicality, and the curve is identically zero beyond it.

Example 10.14 (Bernoulli numbers). For $X \sim Bernoulli (0.1)$ under Hamming distortion, compute $R (0.05)$ and express it as a fraction of the lossless rate.

Solution. $h_{2} (0.1) = - 0.1 lo g_{2} 0.1 - 0.9 lo g_{2} 0.9 = 0.3322 + 0.1368 = 0.4690$ bits.

$h_{2} (0.05) = - 0.05 lo g_{2} 0.05 - 0.95 lo g_{2} 0.95 = 0.2161 + 0.0703 = 0.2864$ bits.

$R (0.05) = 0.4690 - 0.2864 = 0.1826$ bits per symbol.

That is $0.1826/0.4690 = 39%$ of the lossless rate: tolerating a $5%$ symbol error rate has cut the bit budget by nearly two thirds.

Sanity check: $D = 0.05 \leq p = 0.1$ , so the formula applies, and $R$ is positive but well under $h_{2} (p)$ , as it must be for $0 < D < D_{m a x}$ .□

Theorem 10.15 (Gaussian source under squared-error distortion). Let $X \sim N (0, σ^{2})$ and $d (x, \overset{x}{^}) = (x - \overset{x}{^})^{2}$ . Then

R (D) = ⎩ ⎨ ⎧ \frac{1}{2} lo g_{2} \frac{σ ^{2}}{D}, 0, 0 < D \leq σ^{2}, D > σ^{2} .

Proof. Converse. For any $\hat{X}$ with $E [(X - \hat{X})^{2}] \leq D$ ,

I (X; \hat{X}) = h (X) - h (X ∣ \hat{X}) = \frac{1}{2} lo g_{2} (2 π e σ^{2}) - h (X - \hat{X} ∣ \hat{X}) \geq \frac{1}{2} lo g_{2} (2 π e σ^{2}) - h (X - \hat{X}),

because differential entropy is translation invariant given $\hat{X}$ , and conditioning reduces it. Among all random variables with second moment at most $D$ the Gaussian maximizes differential entropy, so $h (X - \hat{X}) \leq \frac{1}{2} lo g_{2} (2 π e E [(X - \hat{X})^{2}]) \leq \frac{1}{2} lo g_{2} (2 π eD)$ . Hence $I (X; \hat{X}) \geq \frac{1}{2} lo g_{2} (σ^{2} / D)$ .

Achievability. Backward channel again: let $\hat{X} \sim N (0, σ^{2} - D)$ and $X = \hat{X} + Z$ with $Z \sim N (0, D)$ independent. Then $X \sim N (0, σ^{2})$ as required, $E [(X - \hat{X})^{2}] = D$ , and $I (X; \hat{X}) = h (X) - h (Z) = \frac{1}{2} lo g_{2} (σ^{2} / D)$ .

The flat part. $D_{m a x} = Var (X) = σ^{2}$ , attained by $\hat{X} \equiv 0$ , so $R (D) = 0$ for $D \geq σ^{2}$ .∎

Remark. Note which direction the noise runs. The backward channel is $X = \hat{X} + Z$ : the source equals the reproduction plus independent noise. The forward channel $p (\overset{x}{^} ∣ x)$ implied by it is not "add noise to $X$ "; it is $\hat{X} = (1 - D / σ^{2}) (X + N)$ for a suitable independent $N$ , a shrunken and noisy copy. The shrinkage factor $1 - D / σ^{2}$ is the MMSE regression coefficient, and it is exactly why a good decoder does not simply invert the quantizer but pulls its output toward the mean.

Intuition. $\frac{1}{2} lo g_{2} (σ^{2} / D)$ says that every halving of the allowed mean squared error costs exactly half a bit per sample — equivalently, every extra bit per sample buys a factor of $4$ in MSE, the familiar $6.02$ dB per bit.

The formula also says the only thing about a Gaussian source that matters is its variance relative to the distortion budget. Scaling the source and the budget together changes nothing.

Example 10.16 (Gaussian numbers and the reconstruction rule). Let $X \sim N (0, 4)$ and $D = 0.5$ . Find $R (D)$ and the variance of the optimal $\hat{X}$ .

Solution. Rate: $R (0.5) = \frac{1}{2} lo g_{2} (4/0.5) = \frac{1}{2} lo g_{2} 8 = 1.5$ bits per sample.

Optimal reproduction: $Var (\hat{X}) = σ^{2} - D = 3.5$ , with $X = \hat{X} + Z$ and $Z \sim N (0, 0.5)$ independent of $\hat{X}$ .

Check by mutual information: $I = h (X) - h (Z) = \frac{1}{2} lo g_{2} (2 π e \cdot 4) - \frac{1}{2} lo g_{2} (2 π e \cdot 0.5) = \frac{1}{2} lo g_{2} 8 = 1.5$ bits, matching.

If the decoder instead holds a noisy observation $Y$ with $X = Y + N$ and $N \sim N (0, D)$ , the MMSE reconstruction is $(1 - D / σ^{2}) Y = 0.875 Y$ .

Sanity check: $D = 0.5 \leq σ^{2} = 4$ , and $Var (\hat{X}) = 3.5 > 0$ , so the construction is legitimate. Had we asked for $D > 4$ the "variance" $σ^{2} - D$ would be negative — the signal that we are past $D_{m a x}$ and the answer is $0$ .□

Theorem 10.17 (The Gaussian source is the hardest one of its variance). Let $X$ have zero mean and variance $σ^{2}$ , and let $d$ be squared error. Then for $0 < D \leq σ^{2}$ ,

R (D) \leq \frac{1}{2} lo g_{2} \frac{σ ^{2}}{D},

with equality if and only if $X$ is Gaussian.

Proof. Put $α = 1 - D / σ^{2} \in [0, 1)$ and define the forward test channel $\hat{X} = α X + W$ with $W \sim N (0, α D)$ independent of $X$ . Its distortion is

E [(X - \hat{X})^{2}] = E [((1 - α) X - W)^{2}] = (1 - α)^{2} σ^{2} + α D = \frac{D ^{2}}{σ ^{2}} + D - \frac{D ^{2}}{σ ^{2}} = D,

so it is feasible. Its mutual information is

I (X; \hat{X}) = h (\hat{X}) - h (\hat{X} ∣ X) = h (α X + W) - h (W) \leq \frac{1}{2} lo g_{2} (2 π e (α^{2} σ^{2} + α D)) - \frac{1}{2} lo g_{2} (2 π e α D),

using the Gaussian maximum-entropy bound on $h (α X + W)$ , whose variance is $α^{2} σ^{2} + α D$ . The right side equals $\frac{1}{2} lo g_{2} \frac{α σ ^{2} + D}{D} = \frac{1}{2} lo g_{2} \frac{σ ^{2}}{D}$ . Since $R (D)$ is a minimum over all feasible channels, $R (D)$ is at most this. Equality in the maximum-entropy step requires $α X + W$ Gaussian, which for independent Gaussian $W$ forces $X$ Gaussian.∎

Figure 10.18. Two rate–distortion curves. Both are convex and decreasing, both reach zero at their own

D_{m a x}

— but the Bernoulli curve starts at the finite entropy

h_{2} (0.1)

, while the Gaussian curve rises without bound as

D \to 0

Remark. This is a design fact and not merely an aesthetic one: if you know only the variance of your source, budgeting $\frac{1}{2} lo g_{2} (σ^{2} / D)$ bits per sample is always enough. Any departure from Gaussianity — sparsity, skew, heavy tails — is free compression waiting to be collected.

Exercises for §10.4 →

10.5The Rate–Distortion Theorem

The last part computed $R^{(I)} (D)$ , an optimization over one-symbol conditional distributions. Nothing so far says that this number has anything to do with codes. That identification is the rate–distortion theorem, and it is the reason the whole subject is called rate–distortion theory rather than "constrained mutual information minimization".

Theorem 10.19 (Rate–distortion theorem). For a discrete memoryless source $X \sim p (x)$ with a bounded distortion measure $d$ ,

R^{(o)} (D) = R^{(I)} (D) for every D \geq D_{m i n} .

That is, the infimum of rates achievable by block codes of any length equals the single-letter minimum $min I (X; \hat{X})$ over test channels meeting the budget. From here on we write $R (D)$ for the common value.

The two halves of the theorem are proved by entirely different arguments. The converse, $R^{(o)} (D) \geq R^{(I)} (D)$ , says no code can beat the formula; it is short, exact, and uses only the properties established above. The achievability, $R^{(o)} (D) \leq R^{(I)} (D)$ , says a code exists; it is a random-coding argument.

Proof. (Converse.) Fix any $(n, 2^{n R})$ code with distortion $E [d (X^{n}, \hat{X}^{n})] \leq D$ , where $\hat{X}^{n} = g_{n} (f_{n} (X^{n}))$ . Let $M = f_{n} (X^{n})$ , a random variable on $2^{n R}$ values. Then

n R \geq H (M) \geq I (X^{n}; M) \geq I (X^{n}; \hat{X}^{n}),

the last step by the data-processing inequality, since $\hat{X}^{n}$ is a function of $M$ . Expand:

I (X^{n}; \hat{X}^{n}) = H (X^{n}) - H (X^{n} ∣ \hat{X}^{n}) = i = 1 \sum n H (X_{i}) - i = 1 \sum n H (X_{i} ∣ \hat{X}^{n}, X^{i - 1}) \geq i = 1 \sum n [H (X_{i}) - H (X_{i} ∣ \hat{X}_{i})],

using independence of the $X_{i}$ for the first sum, the chain rule for the second, and "conditioning reduces entropy" for the inequality. So $I (X^{n}; \hat{X}^{n}) \geq \sum_{i} I (X_{i}; \hat{X}_{i})$ . Let $D_{i} = E [d (X_{i}, \hat{X}_{i})]$ . Each pair $(X_{i}, \hat{X}_{i})$ is a legitimate one-symbol test channel with distortion $D_{i}$ , so $I (X_{i}; \hat{X}_{i}) \geq R^{(I)} (D_{i})$ . Therefore

R \geq \frac{1}{n} i = 1 \sum n R^{(I)} (D_{i}) \geq R^{(I)} (\frac{1}{n} i = 1 \sum n D_{i}) \geq R^{(I)} (D),

where the middle step is Jensen's inequality applied to the convex function $R^{(I)}$ , and the last is monotonicity together with $\frac{1}{n} \sum_{i} D_{i} = E [d (X^{n}, \hat{X}^{n})] \leq D$ . Taking the infimum over codes gives $R^{(o)} (D) \geq R^{(I)} (D)$ .∎

Remark. Look at what the converse did not use. It never assumed the encoder was deterministic, never assumed it looked at the whole block, and never assumed anything about the structure of the codebook. It used exactly three facts: the source is memoryless, $R^{(I)}$ is convex and non-increasing, and $\hat{X}^{n}$ is a function of the message. This robustness is what lets the same argument be recycled almost verbatim for side-information problems later in the chapter.

Proof. (Achievability, sketch.) Fix a test channel $p (\overset{x}{^} ∣ x)$ with $E [d (X, \hat{X})] \leq D - ε$ , and let $p (\overset{x}{^})$ be the induced output marginal. Generate $2^{n R}$ codewords $\hat{X}^{n} (1), \dots, \hat{X}^{n} (2^{n R})$ independently, each drawn i.i.d. from $p (\overset{x}{^})$ , and reveal the codebook to both encoder and decoder. The encoder, seeing $x^{n}$ , sends the index $m$ of any codeword jointly typical with $x^{n}$ under $p (x) p (\overset{x}{^} ∣ x)$ , and sends $m = 1$ if none exists.

The whole argument turns on one counting question: how many independently drawn codewords are needed before one of them is jointly typical with a given $x^{n}$ ? For a fixed typical $x^{n}$ the probability that a single randomly drawn $\hat{X}^{n} \sim \prod p (\overset{x}{^}_{i})$ is jointly typical with it is approximately $2^{- n I (X; \hat{X})}$ , because joint typicality confines the pair to about $2^{n H (X, \hat{X})}$ sequences out of the $2^{n H (X)} 2^{n H (\hat{X})}$ that independent drawing spreads over. With $2^{n R}$ independent attempts, the probability that all fail is about

(1 - 2^{- n I (X; \hat{X})})^{2^{n R}} \approx exp (- 2^{n (R - I (X; \hat{X}))}),

which tends to $0$ when $R > I (X; \hat{X})$ and to $1$ when $R < I (X; \hat{X})$ . This is the covering lemma, and it is the exact mirror image of the packing argument in channel coding: there one needs codewords far enough apart that noise cannot confuse them, here one needs them dense enough that every source sequence has a neighbour.

When the encoder succeeds, joint typicality forces the empirical distortion to be close to $E [d (X, \hat{X})] \leq D - ε$ ; when it fails, the distortion is at most $d_{m a x}$ , an event of vanishing probability, so it contributes $o (1)$ to the average. Hence for every $R > I (X; \hat{X})$ the expected distortion of the random codebook is at most $D$ for large $n$ , and some particular codebook is at least as good as the average. Minimizing over feasible test channels gives $R^{(o)} (D) \leq R^{(I)} (D)$ .

The steps sketched above — the typical-set probability estimate, the concentration of the empirical distortion, and the handling of the failure event — are where the technical work lies; they are standard and are carried out in full in Cover and Thomas, Chapter 10. Boundedness of $d$ is used only to control the failure event, and can be relaxed to a finite-moment condition, which is what makes the squared-error Gaussian case legitimate.∎

Pitfall. The theorem is an asymptotic statement. At block length $n$ there is a penalty of order $lo g n / n$ (the dispersion term), and — more importantly in practice — finding the jointly typical codeword requires searching a codebook of size $2^{n R}$ . The theorem proves existence, not tractability; the rest of the chapter is about what one does instead.

Corollary 10.20 (Source coding theorem). For a discrete memoryless source with $d$ vanishing only on the diagonal, $R^{(o)} (0) = H (X)$ .

Proof. Combine the rate–distortion theorem at $D = 0$ with the earlier proposition computing $R^{(I)} (0) = H (X)$ .∎

Intuition. Think of the codebook as a set of $2^{n R}$ "representative sequences" scattered in the space of all source sequences. The typical set has about $2^{n H (X)}$ members, and each codeword "covers" about $2^{n H (X ∣ \hat{X})}$ of them. To cover everything you need at least $2^{n H (X)} / 2^{n H (X ∣ \hat{X})} = 2^{n I (X; \hat{X})}$ codewords.

Rate–distortion coding is a covering problem; channel coding is a packing problem. That duality is not a metaphor — it is why the same binning construction solves the distributed problems at the end of this chapter.

Exercises for §10.5 →

10.6The Lagrangian Formulation and Blahut–Arimoto

Outside the two closed forms of the previous part, $R (D)$ must be computed numerically. Minimizing $I (X; \hat{X})$ subject to a distortion constraint is a convex program, and the clean way to attack it is to dualize the constraint.

Definition 10.21 (Lagrangian rate–distortion functional). For a multiplier $λ \geq 0$ define

J (λ) = p (\overset{x}{^} ∣ x) min [I (X; \hat{X}) + λ E [d (X, \hat{X})]],

the minimum now unconstrained over all test channels. Writing $Q_{λ}$ for a minimizer and $D_{λ} = E_{Q_{λ}} [d]$ , the pair $(D_{λ}, J (λ) - λ D_{λ})$ is a point on the curve $R (D)$ .

Proposition 10.22 (The multiplier is the slope). $J$ is concave and non-decreasing on $[0, \infty)$ , $J (λ) = R (D_{λ}) + λ D_{λ}$ , and wherever $R$ is differentiable,

R^{'} (D_{λ}) = - λ .

Consequently the slope parameter $s = R^{'} (D) = - λ$ is non-positive, and sweeping $λ$ from $0$ to $\infty$ — equivalently $s$ from $0$ to $- \infty$ — traces the whole curve from $(D_{m a x}, 0)$ down to the left endpoint.

Proof. $J$ is a pointwise minimum of functions affine in $λ$ , hence concave; each such affine function has non-negative slope $E [d] \geq 0$ , so $J$ is non-decreasing. Because the program defining $R (D)$ is convex with a linear constraint and a strictly feasible point whenever $D > D_{m i n}$ , Slater's condition holds and strong duality gives $R (D) = max_{λ \geq 0} [J (λ) - λ D]$ ; the maximizing $λ$ is precisely a negated subgradient of $R$ at $D$ . Evaluating the outer maximum at $D = D_{λ}$ gives $J (λ) = R (D_{λ}) + λ D_{λ}$ , and by the envelope theorem $J^{'} (λ) = D_{λ}$ .∎

Pitfall. Sign conventions here are a classic source of error. The multiplier $λ$ is non-negative and multiplies $E [d]$ with a plus sign; the slope $s = R^{'} (D) = - λ$ is non-positive. Writing the functional as $I + s E [d]$ with $s \leq 0$ would reward large distortion and minimize the wrong thing. If a derivation produces test channel weights $e^{+ λ d}$ — putting more mass on worse reproductions — the sign has been flipped somewhere.

Stationarity of the Lagrangian gives the form of the optimal test channel, and that form is the whole algorithm.

Proposition 10.23 (Form of the optimal test channel). A test channel $p (\overset{x}{^} ∣ x)$ minimizes $I (X; \hat{X}) + λ E [d]$ if and only if, with $q (\overset{x}{^}) = \sum_{x} p (x) p (\overset{x}{^} ∣ x)$ its own output marginal,

p (\overset{x}{^} ∣ x) = \frac{q ( x ^ ) e ^{- λ d (x, \overset{x}{^})}}{\sum _{\overset{x}{^}^{'}} q ( x ^ ^{'} ) e ^{- λ d (x, \overset{x}{^}^{'})}} for all x, \overset{x}{^} .

Proof. Write $F (p, q) = \sum_{x, \overset{x}{^}} p (x) p (\overset{x}{^} ∣ x) [lo g \frac{p ( x ^ ∣ x )}{q ( x ^ )} + λ d (x, \overset{x}{^})]$ , which by the identity used in the convexity lemma satisfies $min_{q} F (p, q) = I (X; \hat{X}) + λ E [d]$ , the minimum at $q = p_{\hat{X}}$ . $F$ is jointly convex, so the joint minimum is characterized by stationarity in each argument. Minimizing over $p (\cdot ∣ x)$ for fixed $q$ with a multiplier $μ (x)$ for the normalization $\sum_{\overset{x}{^}} p (\overset{x}{^} ∣ x) = 1$ gives, for each $x, \overset{x}{^}$ ,

p (x) [lo g \frac{p ( x ^ ∣ x )}{q ( x ^ )} + 1 + λ d (x, \overset{x}{^})] + μ (x) = 0,

so $p (\overset{x}{^} ∣ x) \propto q (\overset{x}{^}) e^{- λ d (x, \overset{x}{^})}$ ; normalizing gives the displayed formula. Minimizing over $q$ for fixed $p$ gives $q = p_{\hat{X}}$ . A point satisfying both conditions simultaneously is exactly the stated fixed point.∎

Method 10.24 (Blahut–Arimoto algorithm). Fix $λ \geq 0$ and an initial distribution $q_{0} (\overset{x}{^})$ with full support. For $k = 0, 1, 2, \dots$ :

Channel update. $p_{k} (\overset{x}{^} ∣ x) = \frac{q _{k} ( x ^ ) e ^{- λ d (x, \overset{x}{^})}}{\sum _{\overset{x}{^}^{'}} q _{k} ( x ^ ^{'} ) e ^{- λ d (x, \overset{x}{^}^{'})}}$ for every $x$ .
Marginal update. $q_{k + 1} (\overset{x}{^}) = x \sum p (x) p_{k} (\overset{x}{^} ∣ x)$ .
Stop when the two successive values of $F$ differ by less than the tolerance.

Then report the point $D_{λ} = E_{p_{k}} [d]$ and $R (D_{λ}) = I_{p_{k}} (X; \hat{X})$ . Sweeping $λ$ over a grid traces the curve.

Theorem 10.25 (Convergence of Blahut–Arimoto). Each iteration does not increase $F$ , and $F (p_{k}, q_{k}) \to J (λ)$ ; the iterates converge to a minimizing pair. Moreover the value $J (λ)$ is approached monotonically, so the algorithm supplies its own upper bound at every step.

Proof. Each of the two updates is an exact minimization of $F$ over one argument with the other held fixed, by the two stationarity computations in the previous proposition. So $F (p_{k}, q_{k}) \geq F (p_{k}, q_{k + 1}) \geq F (p_{k + 1}, q_{k + 1})$ , a non-increasing sequence bounded below by $J (λ) \geq 0$ , hence convergent. That the limit is the global minimum rather than a stalled coordinate point follows from joint convexity of $F$ together with the fact that $F$ is differentiable with full-support iterates: a point that is a minimum in each coordinate of a jointly convex differentiable function is a global minimum. The detailed argument, including the rate of convergence and the extension to unbounded alphabets, is due to Blahut and to Arimoto and is not reproduced here.∎

Intuition. Instead of fixing the distortion budget and minimizing rate, put a price $λ$ on distortion and minimize rate-plus-cost. The optimal test channel then looks like a Boltzmann distribution: reproduction $\overset{x}{^}$ gets weight proportional to how popular it is overall, $q (\overset{x}{^})$ , discounted by $e^{- λ d (x, \overset{x}{^})}$ for how badly it serves this particular $x$ .

Sweeping the price from "distortion is free" ( $λ = 0$ , so $R = 0$ at $D = D_{m a x}$ ) to "distortion is unaffordable" ( $λ \to \infty$ ) draws the whole frontier. And because each iteration is an exact minimization of a jointly convex function, the algorithm cannot get stuck.

Example 10.26 (The slope parameter for a Gaussian source). For $X \sim N (0, σ^{2})$ under squared error, find the slope $s = R^{'} (D)$ at distortion $D$ , and the corresponding multiplier.

Solution. $R (D) = \frac{1}{2} lo g_{2} (σ^{2} / D) = \frac{1}{2 l n 2} (ln σ^{2} - ln D)$ , so

R^{'} (D) = - \frac{1}{2 D ln 2} bits per unit distortion, λ = \frac{1}{2 D ln 2} .

At $D = σ^{2}$ the slope is $- 1/ (2 σ^{2} ln 2)$ , finite, and as $D ↓ 0$ the slope steepens without bound.

Sanity check: the slope is negative and its magnitude increases as $D$ decreases, exactly as convexity of $R$ demands. Note also that this is the price at which one more unit of MSE is worth exactly the bits it saves — which is why $λ$ reappears as the Lagrange multiplier in every practical codec's rate-control loop, where the encoder minimizes $bits + λ \cdot distortion$ over coding modes.□

Exercises for §10.6 →

10.7Bounds, and Parallel Gaussian Sources

Closed forms are rare. What is available for a general source is a pair of bounds that pin $R (D)$ between them, plus an exact answer for the one structured case that matters most in practice: a collection of independent Gaussians of different variances, which is what a transform coder produces.

Theorem 10.27 (Shannon lower bound). Let $X$ be a continuous source on $R$ with $h (X) > - \infty$ , and let $d$ be a difference distortion measure, $d (x, \overset{x}{^}) = ρ (x - \overset{x}{^})$ . Then

R (D) \geq h (X) - max {h (W) : E [ρ (W)] \leq D} .

In particular, for squared error $ρ (u) = u^{2}$ ,

R (D) \geq h (X) - \frac{1}{2} lo g_{2} (2 π eD) .

Proof. For any feasible $\hat{X}$ ,

I (X; \hat{X}) = h (X) - h (X ∣ \hat{X}) = h (X) - h (X - \hat{X} ∣ \hat{X}) \geq h (X) - h (X - \hat{X}),

using translation invariance of differential entropy under a shift by the conditioning variable, then "conditioning reduces differential entropy". The variable $W = X - \hat{X}$ satisfies $E [ρ (W)] \leq D$ , so $h (W)$ is at most the stated maximum. For squared error the maximum-entropy distribution with second moment $D$ is $N (0, D)$ , of differential entropy $\frac{1}{2} lo g_{2} (2 π eD)$ .∎

Remark. The Shannon lower bound is tight in the limit of small $D$ : for squared error, $R (D) - [h (X) - \frac{1}{2} lo g_{2} (2 π eD)] \to 0$ as $D ↓ 0$ for sources with well-behaved densities. It is not tight at large $D$ — indeed it goes negative there while $R (D)$ is $0$ — so it should always be read as $max {0, SLB}$ . Combined with the earlier theorem that the Gaussian is the worst source of its variance, it brackets $R (D)$ for any source:

max {0, h (X) - \frac{1}{2} lo g_{2} (2 π eD)} \leq R (D) \leq \frac{1}{2} lo g_{2} \frac{σ ^{2}}{D},

and the width of that bracket is $\frac{1}{2} lo g_{2} (2 π e σ^{2}) - h (X)$ , the non-Gaussianity of the source, measured in bits. For a Gaussian source it is zero and the bracket collapses to the exact answer.

Example 10.28 (How much is non-Gaussianity worth?). A zero-mean Laplacian source has density $\frac{1}{2 b} e^{- ∣ x ∣/ b}$ , variance $σ^{2} = 2 b^{2}$ and differential entropy $h (X) = lo g_{2} (2 e b)$ bits. How many bits per sample does its non-Gaussianity save at high rate?

Solution. The bracket width is $\frac{1}{2} lo g_{2} (2 π e σ^{2}) - h (X)$ . With $σ^{2} = 2 b^{2}$ ,

\frac{1}{2} lo g_{2} (2 π e \cdot 2 b^{2}) = \frac{1}{2} lo g_{2} (4 π e b^{2}) and h (X) = lo g_{2} (2 e b) = \frac{1}{2} lo g_{2} (4 e^{2} b^{2}) .

The difference is $\frac{1}{2} lo g_{2} \frac{4 π e b ^{2}}{4 e ^{2} b ^{2}} = \frac{1}{2} lo g_{2} \frac{π}{e} = \frac{1}{2} lo g_{2} (1.1557) = 0.1044$ bits per sample.

Sanity check: the number is positive, as it must be — the Gaussian maximizes entropy for a given variance — and it is small, which says a Laplacian is nearly as hard to code as a Gaussian of the same variance. Sparse sources do far better: the saving grows without bound as the density concentrates.□

Theorem 10.29 (Reverse water-filling for parallel Gaussian sources). Let $X_{1}, \dots, X_{m}$ be independent with $X_{j} \sim N (0, σ_{j}^{2})$ , and take the total squared-error distortion $d (x^{m}, \overset{x}{^}^{m}) = \sum_{j = 1}^{m} (x_{j} - \overset{x}{^}_{j})^{2}$ . Then

R (D) = j = 1 \sum m \frac{1}{2} lo g_{2} \frac{σ _{j}^{2}}{D _{j}}, D_{j} = min (θ, σ_{j}^{2}),

where the water level $θ > 0$ is chosen so that $\sum_{j} D_{j} = D$ . Components with $σ_{j}^{2} \leq θ$ receive no bits at all and are reproduced by their mean.

Proof. Converse. For any feasible joint test channel, independence of the components gives

I (X^{m}; \hat{X}^{m}) = h (X^{m}) - h (X^{m} ∣ \hat{X}^{m}) \geq j \sum h (X_{j}) - j \sum h (X_{j} ∣ \hat{X}_{j}) = j \sum I (X_{j}; \hat{X}_{j}) \geq j \sum [\frac{1}{2} lo g_{2} \frac{σ _{j}^{2}}{D _{j}}]^{+},

with $D_{j} = E [(X_{j} - \hat{X}_{j})^{2}]$ and $[\cdot]^{+} = max {\cdot, 0}$ , by the scalar Gaussian theorem applied componentwise. It remains to minimize $\sum_{j} \frac{1}{2} lo g_{2}^{+} (σ_{j}^{2} / D_{j})$ over $D_{j} \geq 0$ with $\sum_{j} D_{j} \leq D$ . The objective is convex and separable; a Lagrange multiplier $λ$ for the budget gives the stationarity condition $- \frac{1}{2 D _{j} l n 2} + λ = 0$ , i.e. $D_{j} = θ := \frac{1}{2 λ l n 2}$ , for every component whose constraint $D_{j} \leq σ_{j}^{2}$ is inactive; components hitting that ceiling take $D_{j} = σ_{j}^{2}$ and contribute zero rate. Together these are exactly $D_{j} = min (θ, σ_{j}^{2})$ .

Achievability. Code the components separately, using an optimal scalar-Gaussian rate–distortion code at distortion $D_{j}$ for component $j$ . The rates add and the distortions add, so the bound is met.∎

Intuition. Ordinary water-filling in channel coding pours power into the strongest sub-channels. Reverse water-filling pours distortion into the weakest components: pick a level $θ$ ; every component with variance above the level is coded down to exactly distortion $θ$ , and every component already quieter than the level is thrown away entirely and replaced by zero.

Two consequences matter in practice. Components are not given equal bit budgets — they are given equal residual distortion. And below the water level the optimal bit allocation is zero, which is the theoretical justification for the zero-runs that dominate a JPEG or AAC bitstream.

Example 10.30 (Reverse water-filling, worked). Four independent Gaussian components have variances $σ^{2} = (4, 2, 1, 0.5)$ and the total distortion budget is $D = 2.5$ . Find the water level, the per-component distortions, and the total rate.

Solution. Try a water level $θ$ below every variance. Then $\sum_{j} D_{j} = 4 θ = 2.5$ gives $θ = 0.625$ , which exceeds $σ_{4}^{2} = 0.5$ — inconsistent, because component $4$ would then lie below the level. So component $4$ is discarded: $D_{4} = σ_{4}^{2} = 0.5$ , and the remaining three share $2.5 - 0.5 = 2.0$ , giving $θ = 2.0/3 = 0.6667$ . Check: $θ = 0.6667 \leq 1, 2, 4$ and $θ > 0.5$ . Consistent.

Distortions: $D = (0.6667, 0.6667, 0.6667, 0.5)$ , summing to $2.5$ . ✓

Rates: $R_{1} = \frac{1}{2} lo g_{2} (4/0.6667) = \frac{1}{2} lo g_{2} 6 = \frac{1}{2} (2.5850) = 1.2925$ ; $R_{2} = \frac{1}{2} lo g_{2} (2/0.6667) = \frac{1}{2} lo g_{2} 3 = \frac{1}{2} (1.5850) = 0.7925$ ; $R_{3} = \frac{1}{2} lo g_{2} (1/0.6667) = \frac{1}{2} lo g_{2} 1.5 = \frac{1}{2} (0.5850) = 0.2925$ ; $R_{4} = 0$ .

Total $R = 1.2925 + 0.7925 + 0.2925 + 0 = 2.3775$ bits for the block of four, i.e. $0.594$ bits per component.

Sanity check: the loudest component gets the most bits and the quietest gets none; every coded component is left with exactly the same residual distortion $0.6667$ ; and the total distortion exhausts the budget.□

Figure 10.31. Reverse water-filling on the four components. Each pale bar is a component variance; the dashed line is the water level

θ = 0.667

; each solid bar is the distortion left in that component. Components above the level are all coded down to exactly

θ

; the fourth, already below it, is discarded whole and given no bits.

Corollary 10.32 (Gaussian vector source). For $X \sim N (0, Σ)$ in $R^{m}$ with total squared-error distortion, $R (D)$ is given by reverse water-filling over the eigenvalues of $Σ$ .

Proof. Let $Σ = U Λ U^{⊤}$ with $U$ orthogonal. The map $X \mapsto U^{⊤} X$ is an orthogonal change of coordinates: it preserves mutual information (being invertible) and preserves squared-error distortion (being an isometry). In the new coordinates the components are independent Gaussians with variances the eigenvalues $λ_{j}$ , and the previous theorem applies.∎

Remark. This corollary is the theoretical charter of transform coding. The Karhunen–Loève transform — the eigenbasis of $Σ$ — turns a correlated vector source into independent components, after which the optimal thing to do is reverse water-filling. Real codecs replace the KLT by a fixed, signal-independent approximation such as the DCT, which is close to the KLT for the near-Markov statistics of natural images and costs $O (m lo g m)$ instead of $O (m^{2})$ .

Exercises for §10.7 →

10.8Blahut–Arimoto in Practice: R(D) for a Binary Source

The algorithm itself was stated in the previous part, as the recipe Blahut–Arimoto algorithm: alternate the channel update $p_{k} (\overset{x}{^} ∣ x) \propto q_{k} (\overset{x}{^}) e^{- λ d (x, \overset{x}{^})}$ with the marginal update $q_{k + 1} (\overset{x}{^}) = \sum_{x} p (x) p_{k} (\overset{x}{^} ∣ x)$ . This part runs it.

Notation (The two ways the multiplier is written). Much of the literature writes the channel update as $p (\overset{x}{^} ∣ x) \propto q (\overset{x}{^}) exp (s d (x, \overset{x}{^}))$ with $s \leq 0$ , rather than with $e^{- λ d}$ and $λ \geq 0$ . These are the same update under $s = - λ$ , which is the identification already made in the proposition the multiplier is the slope: $λ \geq 0$ is the price paid per unit of distortion in the objective $I + λ E [d]$ , and $s = R^{'} (D) = - λ \leq 0$ is the slope of the curve at the converged point.

This chapter minimizes with $λ \geq 0$ and $e^{- λ d}$ , and reports the converged operating point by its slope $s = - λ$ . A run "at $s = - 4.25$ " and a run "at $λ = 4.25$ " are the same run.

Intuition. Start with a guess at what the reproductions look like on average, $q (\overset{x}{^})$ .

Update the best way to map originals to reproductions given that guess, then update the guess to match what the mapping actually produces. Repeat.

The arithmetic is just re-normalizing exponentials of the distortion, down-weighted by $e^{- λ d}$ : it is a soft version of "assign each source symbol to its closest reproduction", with $λ$ controlling how soft.

Example 10.33 (Blahut–Arimoto against a known closed form). Binary source with $Pr [X = 1] = p = 0.1$ and Hamming distortion $d (x, \overset{x}{^}) = 1 [x \neq = \overset{x}{^}]$ . Target $D = 0.05$ and check what the algorithm converges to against the closed form $R (D) = h_{2} (p) - h_{2} (D)$ , valid for $0 \leq D \leq p \leq \frac{1}{2}$ . Logs base 2.

Solution. Closed-form target. $h_{2} (0.1) = 0.4690$ and $h_{2} (0.05) = 0.2864$ , so $R (0.05) = 0.4690 - 0.2864 = 0.1826$ bits.

What the iteration converges to. For this source the optimal test channel is a BSC with crossover $D = 0.05$ : it flips the symbol with probability $0.05$ . Updating $p (\overset{x}{^} ∣ x) \propto q (\overset{x}{^}) e^{- λ d (x, \overset{x}{^})}$ and then re-inducing $q$ drives the effective crossover to $0.05$ for the $λ$ at which $E [d] = 0.05$ .

Reading off the rate. At the fixed point $R = I (X; \hat{X})$ evaluated at that test channel equals $h_{2} (0.1) - h_{2} (0.05) = 0.1826$ bits, matching the closed form.

Checking the slope. The multiplier at convergence must satisfy $s = R^{'} (D) = - λ$ . Here $\frac{d}{d D} [h_{2} (p) - h_{2} (D)] = - lo g_{2} \frac{1 - D}{D} = - lo g_{2} 19 = - 4.2479$ , so the run converges at $λ = 4.2479$ and reports slope $s = - 4.2479$ — negative, as a rate–distortion trade-off requires.

Sanity check: at $D = p = 0.1$ the formula gives $R = h_{2} (0.1) - h_{2} (0.1) = 0$ , and indeed zero rate is achievable by always outputting $\overset{x}{^} = 0$ , incurring distortion exactly $p = 0.1$ . ✓□

Example 10.34 (One channel update by hand). Run a single channel update for that source from $q = (0.5, 0.5)$ at $λ = 2$ , and give $p (\overset{x}{^} = 0 ∣ x = 0)$ .

Solution. The unnormalized weights for $x = 0$ are $q (0) e^{- λ \cdot 0} = 0.5$ and $q (1) e^{- λ \cdot 1} = 0.5 e^{- 2} = 0.067668$ . The normalizer is $0.567668$ , so

p (\overset{x}{^} = 0 ∣ x = 0) = \frac{0.5}{0.567668} = 0.8808.

Sanity check: the matching reproduction is favoured, by the factor $e^{- λ} = 0.1353$ that separates a mismatch from a match — and as $λ \to \infty$ this tends to the hard assignment $p (0 ∣ 0) \to 1$ .□

Exercises for §10.8 →

10.9The Dual Problem: Alternating Minimisation for Channel Capacity

Rate–distortion coding is a covering problem and channel coding is a packing problem, and the two optimizations are duals of each other: one minimizes mutual information over test channels at a fixed source, the other maximizes mutual information over input distributions at a fixed channel. The alternating-minimisation machinery of the previous part does not care which. Arimoto published the capacity iteration and Blahut the rate–distortion one in the same year, and they are the same algorithm; seeing the capacity version is what makes clear that nothing in it was special to distortion. That is why it earns a section here, in a chapter otherwise about $R (D)$ .

For capacity of a DMC with fixed forward channel $p (y ∣ x)$ , the iteration alternates two closed-form steps. Given the current input distribution $p (x)$ :

Compute the induced output $p (y) = \sum_{x} p (x) p (y ∣ x)$ .
Update the input by reweighting each symbol by how "informative" it is, measured by the KL divergence between its output row and the average output:
$p^{'} (x) = \frac{p ( x ) exp ( D ( p ( y ∣ x ) ∥ p ( y ) ) )}{\sum _{x^{'}} p ( x ^{'} ) exp ( D ( p ( y ∣ x ^{'} ) ∥ p ( y ) ) )},$
where $D (p (y ∣ x) ∥ p (y)) = \sum_{y} p (y ∣ x) lo g \frac{p ( y ∣ x )}{p ( y )}$ is exactly $I (x; Y)$ , the mutual information contributed by input symbol $x$ .

Symbols whose output row stands out from the average (large divergence) get boosted; symbols that look like the crowd get suppressed. The normalization keeps $p^{'} (x)$ a valid pmf. Note the sign: here the exponent is $+ D (\cdot ∥ \cdot)$ , because this problem is a maximization — the mirror image of the $e^{- λ d}$ that down-weights bad reproductions in the $R (D)$ iteration.

Proposition 10.35 (Fixed point of the capacity iteration). At the fixed point the KKT conditions hold: every symbol with $p (x) > 0$ has the same value $I (x; Y) = C$ , and every unused symbol has $I (x; Y) \leq C$ .

Inputs with lower $I (x; Y)$ are therefore driven to probability zero — the iteration prunes the alphabet as it goes. This is the exact counterpart of the stationarity condition for the optimal test channel: in both problems the fixed point is characterized by every active coordinate carrying the same marginal value.

Intuition. Guess a distribution on what you send.

Compute what comes out, and how much information each possible input explains about the output.

Reweight your guess toward the inputs that carried more information. Repeat until the distribution stabilizes on the best inputs.

Example 10.36 (The Z-channel). Input $0$ is always received as $0$ ; input $1$ is flipped to $0$ with probability $e = 0.5$ and received correctly with probability $1 - e = 0.5$ . So $p (0 ∣ 0) = 1$ , $p (0 ∣ 1) = 0.5$ , $p (1 ∣ 1) = 0.5$ . Logs base 2. Write $a = Pr [X = 1]$ ; find the capacity and verify the fixed point.

Solution. Induced output. $Pr [Y = 1] = a (1 - e) = 0.5 a$ and $Pr [Y = 0] = 1 - 0.5 a$ . Conditional output entropy: $H (Y ∣ X) = (1 - a) \cdot 0 + a \cdot h_{2} (e) = a h_{2} (0.5) = a$ , since only $X = 1$ injects noise and $h_{2} (0.5) = 1$ .

Mutual information. $I (a) = H (Y) - H (Y ∣ X) = h_{2} (0.5 a) - a$ .

Optimize — what the iteration converges to. Setting $I^{'} (a) = 0$ gives the closed form $a^{⋆} = \frac{1}{( 1 - e ) ( 1 + 2 ^{h_{2} (e) / (1 - e)} )} = \frac{1}{0.5 ( 1 + 2 ^{2} )} = \frac{1}{0.5 \cdot 5} = 0.4$ . Note $a^{⋆} = 0.4 \neq = 0.5$ : the asymmetry pushes the optimal input off uniform, and the iteration discovers this automatically.

Capacity. With $a^{⋆} = 0.4$ : $Pr [Y = 1] = 0.2$ , so $C = h_{2} (0.2) - 0.4 = 0.7219 - 0.4 = 0.3219$ bits.

Verify the KKT fixed point. At $a^{⋆}$ , each supported input must satisfy $I (x; Y) = D (p (y ∣ x) ∥ p (y)) = C$ . For $x = 0$ : $D = 1 \cdot lo g_{2} \frac{1}{0.8} = 0.3219$ . For $x = 1$ : $D = 0.5 lo g_{2} \frac{0.5}{0.8} + 0.5 lo g_{2} \frac{0.5}{0.2} = 0.3219$ . Both equal $C$ . ✓ This equality is exactly the fixed-point condition that stops the iteration.

Sanity check: the uniform input gives $I (0.5) = h_{2} (0.25) - 0.5 = 0.8113 - 0.5 = 0.3113$ bits, short of $C$ by $0.0106$ bits — the gap the iteration closes by moving mass toward $a^{⋆}$ .□

Exercises for §10.9 →

10.10Convergence, Numerics, and Practical Use

That both iterations converge to the global optimum is the content of the theorem convergence of Blahut–Arimoto: each step is an exact minimization of a jointly convex function over one argument, so the objective is non-increasing and cannot stall anywhere but the optimum. Nothing further needs to be proved here. What remains is the practical side — when to stop, and how to keep the arithmetic from overflowing.

Stopping. Stop when the change in $R$ (or in $C$ ), or in the distributions themselves, falls below a tolerance. Because the objective is approached monotonically, the current value is always a valid upper bound on $J (λ)$ , so the iterate in hand is never worse than it looks.

Numerical hygiene. Compute $e^{- λ d}$ in the log domain and subtract the row maximum before exponentiating — a log-sum-exp. With large $λ$ and large distortions the raw exponentials underflow to zero and the row normalization becomes $0/0$ .

Beyond the basic iteration. Modern variants use accelerated methods, stochastic approximations for very large alphabets, or discretize a continuous source and combine the iteration with neural networks; the alternating "posterior then marginal" structure reappears in variational autoencoders and in learned image and video compression. The same alternating-minimisation idea also underlies the EM algorithm and expectation propagation.

Intuition. Because the problem is bowl-shaped, no matter where you start the iteration rolls downhill to the same bottom.

In code you keep updating two arrays — the conditional and the marginal — until they stop changing much; the final mutual information is your answer.

Example 10.37 (What does one point of the curve cost?). Estimate the cost of computing $R (D)$ for a $256$ -ary source (say an 8-bit image pixel histogram) with $256$ reproduction levels and a chosen $256 \times 256$ distortion matrix.

Solution. Cost per iteration. Each iteration makes two passes over the $256 \times 256$ conditional array: one to update $p (\overset{x}{^} ∣ x) \propto q (\overset{x}{^}) e^{- λ d (x, \overset{x}{^})}$ with a row normalization, one to re-induce $q (\overset{x}{^}) = \sum_{x} p (x) p (\overset{x}{^} ∣ x)$ . That is $Θ (25 6^{2}) = Θ (65, 536)$ multiply-adds per iteration, touching $131, 072$ array entries — microseconds on a laptop.

Iteration count. Convergence is linear; for small-to-moderate alphabets, driving the change below $1 0^{- 3}$ bits typically takes tens to a few hundred iterations. Say $\sim 200$ here.

Total work. $200 \times 65, 536 = 1.31 \times 1 0^{7}$ operations for one point on the curve — a fraction of a second. Sweeping $\sim 50$ values of $λ$ to trace the whole $R (D)$ curve costs $6.55 \times 1 0^{8}$ operations, still well under a minute.

Sanity check: verify $s = - λ$ against $d R / d D$ at each converged point by finite-differencing neighbouring $(R, D)$ pairs. Agreement confirms the iteration reached a genuine stationary point rather than stopping early. ✓□

Exercises for §10.10 →

Common Mistakes

Getting the Lagrangian sign backwards. Minimize $I + λ E [d]$ with $λ \geq 0$ ; the slope of the curve is $s = R^{'} (D) = - λ \leq 0$ . Optimal test channel weights carry $e^{- λ d} = e^{s d}$ , never $e^{+ λ d}$ — that would put more mass on worse reproductions. Writing the objective itself as $I + s E [d]$ with $s \leq 0$ minimizes the wrong thing.
Losing track of which of $λ$ and $s$ is being quoted. They differ only in sign, but a run reported "at $s = - 4.25$ " and one reported "at $λ = 4.25$ " are the same run, and mixing the two inside one derivation is the commonest arithmetic slip in the subject.
Forgetting to normalize the test-channel updates. The proportionality must become a true conditional pmf for each $x$ ; a missing normalization silently ruins the computed $I$ .
Running the algorithm at a fixed $D$ instead of sweeping the multiplier. Direct fixed- $D$ variants exist, but the Lagrangian form is numerically more stable and traces the whole curve as a by-product.
Ignoring that $s = R^{'} (D)$ at the solution. After convergence the slope can be read off the final multiplier and checked against a finite difference of neighbouring points — the cheapest available test that the iteration actually converged.
Exponentiating outside the log domain. With $λ ≫ 1$ the weights $e^{- λ d}$ underflow to zero; subtract the row maximum first.
Assuming convergence from any initialization without checking. Convexity guarantees it for the exact iteration, but floating-point and approximate versions on large problems can still need several starts. Initializing $q_{0}$ with full support is not optional: a reproduction symbol given zero mass can never regain it.
Confusing the algorithm with code construction. It gives the information-theoretic limit $R (D)$ or $C$ ; it does not produce encoder and decoder codebooks, though it can guide quantizer design.
Using it on continuous alphabets without discretization. The iteration is for finite alphabets; continuous problems need discretization, kernel methods, or parametric assumptions.
Reading the achievability proof as an algorithm. It proves a good codebook exists by averaging over random codebooks; it offers no way to find one, and the encoding step it describes is a search over $2^{n R}$ codewords.
Confusing $R (D)$ with the distortion–rate function $D (R)$ . They are inverse functions of each other on the range where $R$ is strictly decreasing: $R (D)$ is the least rate for a distortion budget, $D (R)$ the least distortion for a rate budget. Quoting one where the other is meant inverts every inequality.
Asserting $R (0) = H (X)$ for every source. It holds for discrete sources with a distortion measure vanishing only on the diagonal. For a continuous source $R (D) \to \infty$ as $D \to 0$ , and substituting the differential entropy $h (X)$ for $H (X)$ is wrong — $h (X)$ can even be negative.
Using $h_{2} (p) - h_{2} (D)$ outside $D \leq min (p, 1 - p)$ . Past $D_{m a x}$ the true value is $0$ ; the formula goes negative and is meaningless there.
Forgetting that $R (D)$ depends on the distortion measure as much as on the source. Swapping squared error for absolute error or a perceptual metric changes the function entirely; a rate–distortion claim with no $d$ attached is not a claim.
Treating the test channel as a physical channel. $p (\overset{x}{^} ∣ x)$ scores a proposed source–reproduction relationship; nothing is transmitted through it and it need not be implementable.
Assuming the optimal reproduction alphabet equals the source alphabet. For a discrete source the optimal $\hat{X}$ can be strictly smaller, and for a continuous source it is a finite set at each finite rate.
Using the Shannon lower bound without clipping it at zero. For $D$ near or above $D_{m a x}$ the expression $h (X) - \frac{1}{2} lo g_{2} (2 π eD)$ is negative, while $R (D) = 0$ . The bound is $max {0, SLB}$ .
Applying the high-rate approximation $R (D) \approx h (X) - \frac{1}{2} lo g_{2} (2 π eD)$ at low rate. It is an asymptotic statement as $D \to 0$ ; at moderate $D$ it can be badly off, and above $D_{m a x}$ it is simply wrong.
Forward water-filling instead of reverse. Channel coding allocates power preferentially to strong sub-channels; rate–distortion allocates distortion equally down to a level and abandons everything below it. The two pictures are not the same, and confusing them inverts the bit allocation.
Assuming a component below the water level should get "a few" bits. The optimum gives it exactly zero and reproduces it by its mean; spending bits there provably wastes them.
Treating $R (D)$ as a per-block quantity. It is bits per source symbol; a block of $n$ symbols needs about $n R (D)$ bits, and the $o (n)$ correction is what finite-blocklength analysis quantifies.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter