46.05.02 · information-theory / side-information

Wyner-Ziv Coding: Rate-Distortion With Side Information at the Decoder

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.5-15.9; Wyner & Ziv 1976 The Rate-Distortion Function for Source Coding with Side Information at the Decoder; Wyner 1978 The Rate-Distortion Function for Source Coding with Side Information at the Decoder II

Intuition Beginner

You want to send a photo to your friend, but your friend already has a low-resolution version of the same photo. How many bits do you need to send so your friend can reconstruct a high-resolution version?

If your friend had no prior information, you would need to send enough bits to encode the full photo — that is the standard rate-distortion problem. But your friend has the low-res version, which is highly correlated with the high-res version. You should be able to exploit this correlation to send fewer bits.

The catch: you (the encoder) do not know exactly what low-res version your friend has. You know the statistics of the correlation, but not the specific realization. So you cannot simply send the difference. You must design a code that works for all possible side information values at the decoder.

Wyner-Ziv coding solves this problem. The Wyner-Ziv rate-distortion function $R_{W Z} (D)$ gives the minimum rate needed when side information $Y$ is available at the decoder but not at the encoder. If side information were available at both ends, the rate would be $R_{X ∣ Y} (D)$ — the conditional rate-distortion function. Without side information at all, the rate would be the standard $R_{X} (D)$ .

The Wyner-Ziv rate satisfies $R_{X ∣ Y} (D) \leq R_{W Z} (D) \leq R_{X} (D)$ . Side information at the decoder helps, but not as much as side information at both ends — unless the source and side information are jointly Gaussian with quadratic distortion, in which case $R_{W Z} (D) = R_{X ∣ Y} (D)$ and decoder-only side information is just as good.

Visual Beginner

Figure: three scenarios for compressing source $X$ with correlated side information $Y$ . Left: no side information — rate is $R_{X} (D)$ . Center: side information at both encoder and decoder — rate is $R_{X ∣ Y} (D)$ . Right: side information at decoder only — rate is $R_{W Z} (D)$ , between the other two.

Scenario	Side info at encoder?	Side info at decoder?	Rate
Standard rate-distortion	No	No	$R_{X} (D)$
Conditional rate-distortion	Yes	Yes	$R_{X
Wyner-Ziv	No	Yes	$R_{W Z} (D)$

The Wyner-Ziv rate is always between the conditional and unconditional rate-distortion functions.

Worked example Beginner

A source $X$ is a fair coin flip (0 or 1). The side information $Y$ equals $X$ with probability 0.9 and flips with probability 0.1. We want to reconstruct $X$ with Hamming distortion $D = 0$ (lossless).

Without side information: $R_{X} (0) = H (X) = 1$ bit per symbol. With side information at both ends: $R_{X ∣ Y} (0) = H (X ∣ Y) = H (0.1) \approx 0.469$ bits per symbol. Wyner-Ziv: $R_{W Z} (0) = H (X ∣ Y) \approx 0.469$ bits per symbol (since lossless Wyner-Ziv reduces to the Slepian-Wolf conditional entropy rate).

In this case, the Wyner-Ziv rate equals the conditional rate-distortion function. The encoder does not need to see $Y$ to achieve the best possible rate. This is because at zero distortion, the problem reduces to Slepian-Wolf coding, where decoder-only side information is sufficient.

For distortion $D > 0$ , the Wyner-Ziv rate can be strictly larger than $R_{X ∣ Y} (D)$ . The rate penalty for not having side information at the encoder is the cost of not being able to adapt the compression to the specific side information value.

Check your understanding Beginner

Formal definition Intermediate+

Let $(X, Y)$ be correlated random variables with joint distribution $p (x, y)$ on $X \times Y$ , and let $d : X \times \hat{X} \to [0, \infty)$ be a distortion measure.

Definition (Wyner-Ziv code). A $(2^{n R}, n)$ Wyner-Ziv code consists of:

An encoder $f : X^{n} \to {1, \dots, 2^{n R}}$ mapping the source sequence to an index (without seeing $Y^{n}$ ).
A decoder $g : {1, \dots, 2^{n R}} \times Y^{n} \to \hat{X}^{n}$ mapping the index and the side information sequence to a reconstruction.

The expected distortion is $D = \frac{1}{n} E [d (X^{n}, \hat{X}^{n})]$ .

Definition (Wyner-Ziv rate-distortion function). The Wyner-Ziv rate-distortion function is:

R_{W Z} (D) = p (u ∣ x) \overset{x}{^} = \overset{x}{^} (u, y) E [d (X, \hat{X})] \leq D min [I (X; U) - I (Y; U)],

where the minimum is over auxiliary random variables $U$ such that $X \to U \to Y$ does not form a Markov chain (but $U$ is conditionally independent of $Y$ given $X$ , i.e., $Y \to X \to U$ ), and $\hat{X}$ is a deterministic function of $(U, Y)$ .

Key theorem with proof Intermediate+

Theorem (Wyner-Ziv 1976). The Wyner-Ziv rate-distortion function $R_{W Z} (D)$ is the infimum of rates $R$ such that there exists a sequence of $(2^{n R}, n)$ codes with expected distortion $\leq D$ .

Proof sketch (achievability). Choose $p (u ∣ x)$ and $\overset{x}{^} (u, y)$ achieving $R_{W Z} (D)$ . Generate $2^{n R}$ auxiliary codewords $U^{n} (w)$ for $w = 1, \dots, 2^{n R}$ by drawing each symbol i.i.d. from $p (u)$ . Partition the codewords into $2^{n (I (X; U) - I (Y; U) + ϵ)}$ bins of size $2^{n (I (Y; U) - ϵ)}$ .

Encoder: Given $X^{n}$ , find a codeword $U^{n} (w)$ that is jointly typical with $X^{n}$ . Send the bin index of $w$ .

Decoder: Given bin index and $Y^{n}$ , find the unique codeword $U^{n} (\tilde{w})$ in the declared bin that is jointly typical with $Y^{n}$ . Reconstruct $\hat{X}^{n}$ via $\overset{x}{^}_{i} = \overset{x}{^} (\tilde{u}_{i}, y_{i})$ .

Error analysis: The encoder finds a typical codeword with high probability if $R > I (X; U)$ . The decoder resolves the correct codeword from the bin because the number of codewords per bin ( $2^{n (I (Y; U) - ϵ)}$ ) is large enough that the jointly typical one with $Y^{n}$ is unique with high probability. The rate is $I (X; U) - I (Y; U) + ϵ$ .

Distortion: By the law of large numbers, the empirical distortion of $\hat{X}^{n}$ approaches $E [d (X, \hat{X} (U, Y))] \leq D$ . $□$

Bridge. The Wyner-Ziv theorem builds toward the Berger-Tung inner bound for distributed lossy compression, which generalises Wyner-Ziv to multiple correlated sources with individual distortion constraints. This is exactly the lossy counterpart of the Slepian-Wolf theorem 46.05.01, where the conditional entropy $H (X ∣ Y)$ is replaced by $I (X; U) - I (Y; U)$ and the lossless constraint gives way to a distortion constraint. The result appears again in the Gelfand-Pinsker theorem 46.05.03 as a channel-coding dual: in Wyner-Ziv, the decoder uses side information to resolve the correct reconstruction from a bin; in Gelfand-Pinsker, the encoder uses side information to pre-cancel known interference. The foundational reason the Wyner-Ziv rate exceeds $R_{X ∣ Y} (D)$ in general is that the encoder, not seeing $Y$ , must hedge against all possible side information values, but binning partially compensates by letting the decoder resolve the ambiguity. Putting these together, the central insight is that decoder-only side information provides a rate gain over no side information but incurs a penalty relative to encoder-decoder side information, and the penalty vanishes for the quadratic Gaussian case.

Exercises Intermediate+

Exercise (hard, short answer).

Show that for the quadratic Gaussian Wyner-Ziv problem, $R_{W Z} (D) = \frac{1}{2} lo g \frac{σ _{N}^{2}}{D}$ where $σ_{N}^{2} = Var (X ∣ Y)$ is the conditional variance, for $0 < D < σ_{N}^{2}$ .

Hint

Choose $U = X + V$ where $V \sim N (0, σ_{V}^{2})$ independent of $(X, Y)$ , and the MMSE estimate $\hat{X} = E [X ∣ U, Y]$ .

Answer

Let $U = X + V$ with $V \sim N (0, σ_{V}^{2})$ independent of $(X, Y)$ . Then $Y \to X \to U$ holds. The decoder computes $\hat{X} = E [X ∣ U, Y]$ , which is the MMSE estimate from $(U, Y)$ . By the orthogonality principle, the MSE is $Var (X ∣ U, Y)$ . For jointly Gaussian $(X, Y, U)$ , this conditional variance is:

$Var (X ∣ U, Y) = (\frac{1}{σ ^{2}} + \frac{1}{σ _{N}^{2}} + \frac{1}{σ _{V}^{2}})^{- 1}$

where $σ_{N}^{2} = Var (X ∣ Y)$ . The rate is $I (X; U) - I (Y; U) = \frac{1}{2} lo g \frac{σ ^{2} + σ _{V}^{2}}{σ _{V}^{2}} - \frac{1}{2} lo g \frac{σ _{N}^{2} + σ _{V}^{2}}{σ _{V}^{2}} = \frac{1}{2} lo g \frac{σ ^{2} + σ _{V}^{2}}{σ _{N}^{2} + σ _{V}^{2}}$ . Setting the distortion $D$ equal to $Var (X ∣ U, Y)$ and solving for the rate gives $R = \frac{1}{2} lo g (σ_{N}^{2} / D)$ , which matches $R_{X ∣ Y} (D)$ .

Exercise (hard, short answer).

Prove the Wyner-Ziv converse: $R_{W Z} (D) \geq I (X; U) - I (Y; U)$ for any achievable rate at distortion $D$ , where $U$ is the encoder output index.

Hint

Use the data processing inequality and the Markov chain structure.

Answer

Let $W = f (X^{n})$ be the encoder output (index) and $\hat{X}^{n} = g (W, Y^{n})$ be the decoder output. Define $U_{i} = (W, Y^{i - 1}, Y_{i + 1}^{n})$ as the auxiliary variable for time $i$ . Then $Y_{i} \to X_{i} \to U_{i}$ forms a Markov chain (since $W$ depends on $X^{n}$ only, not on $Y^{n}$ , and $Y^{i - 1}$ and $Y_{i + 1}^{n}$ are independent of $X_{i}$ given $X^{i - 1}$ and $X_{i + 1}^{n}$ ). The reconstruction $\hat{X}_{i}$ is a function of $(W, Y^{n}) \supseteq (U_{i}, Y_{i})$ .

By the chain rule: $n R \geq H (W) \geq I (X^{n}; W ∣ Y^{n}) = H (X^{n} ∣ Y^{n}) - H (X^{n} ∣ W, Y^{n})$ . Since $\hat{X}^{n}$ is a function of $(W, Y^{n})$ , $H (X^{n} ∣ W, Y^{n}) \leq H (X^{n} ∣ \hat{X}^{n})$ . Using Fano and the distortion constraint: $H (X^{n} ∣ \hat{X}^{n}) \leq n δ (D)$ for some function $δ$ . This gives $n R \geq H (X^{n} ∣ Y^{n}) - n δ (D) = n H (X ∣ Y) - n δ (D)$ , which is a weak bound. The tighter bound uses the single-letterization with the auxiliary $U_{i}$ : $n R \geq I (X^{n}; W) - I (Y^{n}; W) = \sum_{i} [I (X_{i}; U_{i}) - I (Y_{i}; U_{i})]$ by the standard single-letterization argument, giving $R \geq I (X; U) - I (Y; U)$ .

Lean formalization Intermediate+

Mathlib does not formalize rate-distortion theory, the Wyner-Ziv function, or the auxiliary-variable achievability argument. The Wyner-Ziv function involves a double minimization over auxiliary random variables $U$ and deterministic reconstruction functions $\overset{x}{^} (u, y)$ subject to a distortion constraint. The achievability proof requires random codebooks of auxiliary codewords, binning, and joint typicality decoding with side information. None of these structures exist in Mathlib. The converse uses a single-letterization argument with carefully constructed auxiliary variables. This unit ships without formalization.

Advanced results Master

The quadratic Gaussian Wyner-Ziv theorem

The most important special case is the quadratic Gaussian Wyner-Ziv problem. When $X$ and $Y$ are jointly Gaussian and the distortion measure is mean-square error, the Wyner-Ziv rate-distortion function equals the conditional rate-distortion function:

R_{W Z} (D) = R_{X ∣ Y} (D) = \frac{1}{2} lo g \frac{σ _{N}^{2}}{D}, 0 < D < σ_{N}^{2},

where $σ_{N}^{2} = Var (X ∣ Y) = σ_{X}^{2} σ_{Z}^{2} / (σ_{X}^{2} + σ_{Z}^{2})$ for the model $Y = X + Z$ with $Z \sim N (0, σ_{Z}^{2})$ .

This means that for the quadratic Gaussian case, there is no rate penalty for not having side information at the encoder. The decoder can extract all the useful information from $Y$ without the encoder knowing the specific value of $Y$ . The proof uses the test channel $U = X + V$ where $V$ is independent Gaussian noise, and the decoder uses the MMSE estimate $\hat{X} = E [X ∣ U, Y]$ .

The Wyner-Ziv rate loss

The rate loss $R_{W Z} (D) - R_{X ∣ Y} (D)$ measures the penalty for lacking encoder side information. Zamir and Berger (1999) showed that for any source and any distortion measure:

0 \leq R_{W Z} (D) - R_{X ∣ Y} (D) \leq \overset{x}{^} (y) min E [d (X, \overset{x}{^} (Y))],

and for the quadratic Gaussian case, the rate loss is exactly zero. For discrete sources with Hamming distortion, the rate loss is at most $H (X ∣ Y)$ bits, and can be strictly positive.

The zero rate loss for the quadratic Gaussian case is intimately connected to the fact that the optimal Wyner-Ziv test channel produces an auxiliary variable $U$ that is "coset representative" of $X$ modulo the side information $Y$ — the encoder sends enough information about $X$ that, combined with $Y$ , the decoder can pin down $X$ to within distortion $D$ .

The Berger-Tung inner bound

The Berger-Tung inner bound generalizes Wyner-Ziv to multiple correlated sources with individual distortion constraints. For two sources $(X_{1}, X_{2})$ with distortion constraints $(D_{1}, D_{2})$ :

R_{1} \geq I (X_{1}; U_{1} ∣ U_{2}), R_{2} \geq I (X_{2}; U_{2} ∣ U_{1}), R_{1} + R_{2} \geq I (X_{1}, X_{2}; U_{1}, U_{2}),

where $U_{1}$ and $U_{2}$ are auxiliary variables satisfying $U_{i} \to X_{i} \to X_{j} \to U_{j}$ (long Markov chain), and $\hat{X}_{i}$ is a function of $(U_{1}, U_{2})$ with $E [d_{i} (X_{i}, \hat{X}_{i})] \leq D_{i}$ .

The Berger-Tung bound is tight for the quadratic Gaussian case (by the same argument as Wyner-Ziv) but is not known to be tight in general. The gap between the Berger-Tung inner bound and the outer bound (cut-set bound) is one of the major open problems in network information theory.

Synthesis. The Wyner-Ziv theorem is the central result on lossy compression with decoder-only side information, establishing that $R_{X ∣ Y} (D) \leq R_{W Z} (D) \leq R_{X} (D)$ with equality $R_{W Z} (D) = R_{X ∣ Y} (D)$ for the quadratic Gaussian case. The central insight is that binning of auxiliary codewords lets the decoder resolve ambiguity using its side information, achieving rate $I (X; U) - I (Y; U)$ where the difference represents the "net information" about $X$ that $Y$ does not already provide. The result generalises to the Berger-Tung bound for multiple sources, building toward distributed lossy compression 46.06.01. The foundational reason the Gaussian case achieves no rate loss is that the MMSE estimator is linear, so the encoder need not adapt to the specific side information value. Putting these together, the Wyner-Ziv theorem reveals a deep asymmetry: side information at the decoder is almost as valuable as side information at both ends for Gaussian sources, but for general sources, the encoder pays a penalty for not seeing the side information.

Full proof set Master

Proposition (Wyner-Ziv achievability). For any $p (u ∣ x)$ and reconstruction function $\overset{x}{^} (u, y)$ with $E [d (X, \hat{X})] \leq D$ and $Y \to X \to U$ , the rate $R = I (X; U) - I (Y; U)$ is achievable with distortion $D$ .

Proof. Codebook generation. Generate $2^{n (I (X; U) + ϵ)}$ codewords $U^{n} (w)$ by drawing each symbol i.i.d. from the marginal $p (u)$ . Randomly partition the codewords into $2^{n R}$ bins of size $2^{n (I (Y; U) - ϵ)}$ .

Encoding. Given $X^{n}$ , find $w$ such that $(X^{n}, U^{n} (w)) \in T_{ϵ}^{(n)}$ . By the covering lemma, such a codeword exists with high probability since the codebook has $2^{n I (X; U)}$ codewords. Send the bin index $b (w)$ .

Decoding. Given bin index $b (w)$ and $Y^{n}$ , find the unique $\tilde{w}$ in bin $b (w)$ such that $(U^{n} (\tilde{w}), Y^{n}) \in T_{ϵ}^{(n)}$ . By the packing lemma, this is unique with high probability because the bin has $2^{n I (Y; U)}$ codewords and there is at most one jointly typical with $Y^{n}$ .

Reconstruction. Set $\overset{x}{^}_{i} = \overset{x}{^} (\tilde{u}_{i}, y_{i})$ . By the law of large numbers, $\frac{1}{n} \sum d (x_{i}, \overset{x}{^}_{i}) \to E [d (X, \hat{X})] \leq D$ .

Rate. The number of bins is $2^{n R} = 2^{n (I (X; U) + ϵ)} / 2^{n (I (Y; U) - ϵ)} = 2^{n (I (X; U) - I (Y; U) + 2 ϵ)}$ . Taking $ϵ \to 0$ , the rate approaches $I (X; U) - I (Y; U)$ . $□$

Connections Master

46.05.01 — Slepian-Wolf coding is the lossless ( $D = 0$ ) limit of Wyner-Ziv; the Wyner-Ziv rate at zero distortion equals $H (X ∣ Y)$ .
46.02.05 — Rate-distortion theory provides $R_{X} (D)$ and $R_{X ∣ Y} (D)$ , the benchmarks that bound $R_{W Z} (D)$ from above and below.
46.05.03 — Gelfand-Pinsker is the channel-coding dual: encoder side information reduces required channel rate, while Wyner-Ziv shows decoder side information reduces required source rate.
46.05.04 — Wyner's common information $C (X; Y)$ measures the minimum rate of shared randomness needed for distributed generation, connecting to the Wyner-Ziv framework.
46.06.01 — The Berger-Tung bound generalizes Wyner-Ziv to distributed lossy compression of multiple sources, and the MAC capacity region is the dual.

Historical & philosophical context Master

Aaron Wyner and Jacob Ziv published "The Rate-Distortion Function for Source Coding with Side Information at the Decoder" in the IEEE Transactions on Information Theory (IT-22, 1976, 1-10). The paper resolved a natural question arising from the Slepian-Wolf theorem (1973): if side information at the decoder helps for lossless compression, how much does it help for lossy compression?

The answer was surprising. The Wyner-Ziv rate-distortion function involves an auxiliary random variable $U$ and takes the form $I (X; U) - I (Y; U)$ , which is strictly larger than the conditional rate-distortion function $R_{X ∣ Y} (D)$ in general. This means there is a genuine rate penalty for not having side information at the encoder. However, for the quadratic Gaussian case, the penalty vanishes — a result that has profound practical implications because Gaussian models are widely used in image and video compression.

Wyner followed up with a second paper in 1978 (IEEE Trans. IT-24, 341-346) strengthening the converse and establishing tighter bounds on the rate loss. The result was extended to multiple sources by Berger and Tung independently in the late 1970s, giving the Berger-Tung inner bound that remains the best known achievable region for distributed lossy compression.

Ram Zamir's 1999 paper "On the Rate Loss of Wyner-Ziv Coding" (with Berger) showed that the rate loss is bounded by 0.5 bits for the quadratic Gaussian case (tight bound), and more generally provided universal upper bounds on the Wyner-Ziv rate loss. This result quantified exactly how much one pays for not having encoder side information.

Bibliography Master

@article{wyner-ziv1976,
  author  = {Wyner, A. D. and Ziv, J.},
  title   = {The Rate-Distortion Function for Source Coding with Side Information at the Decoder},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-22},
  pages   = {1--10},
  year    = {1976},
}
@article{wyner1978,
  author  = {Wyner, A. D.},
  title   = {The Rate-Distortion Function for Source Coding with Side Information at the Decoder {II}},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-24},
  pages   = {341--346},
  year    = {1978},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@article{zamir-berger1999,
  author  = {Zamir, R. and Berger, T.},
  title   = {On the Rate Loss of Wyner-Ziv Coding},
  journal = {IEEE Transactions on Information Theory},
  volume  = {45},
  pages   = {1105--1109},
  year    = {1999},
}

Prerequisites

46.05.01
46.02.05

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.5 (lossy compression when the decoder has extra information, the Wyner-Ziv rate penalty)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.5-15.6 (the Wyner-Ziv theorem, rate-distortion with side information, achievability via forward channel and binning)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.5-15.9; Wyner & Ziv 1976 The Rate-Distortion Function for Source Coding with Side Information at the Decoder; Wyner 1978 The Rate-Distortion Function for Source Coding with Side Information at the Decoder II

References

Wyner, A. D. & Ziv, J. — The Rate-Distortion Function for Source Coding with Side Information at the Decoder · IEEE Transactions on Information Theory IT-22 (1976) 1-10; the original paper establishing the Wyner-Ziv rate-distortion function $R_{W Z} (D) = min_{p (\overset{x}{^} ∣ x)} min_{p (u ∣ x, \overset{x}{^})} [I (X; U) - I (Y; U)]$ subject to $E [d (X, \hat{X})] \leq D$ , showing that side information at the decoder reduces the rate but may not eliminate the rate penalty compared to side information at both encoder and decoder.
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 15.5: the Wyner-Ziv problem, the rate-distortion function with side information, the achievability proof using a forward channel $p (u ∣ x)$ and random binning of $U^{n}$ sequences. Section 15.6: the converse proof, showing that $R_{W Z} (D) \geq R_{X ∣ Y} (D)$ with equality for the quadratic Gaussian case.
Wyner, A. D. — The Rate-Distortion Function for Source Coding with Side Information at the Decoder II · IEEE Transactions on Information Theory IT-24 (1978) 341-346; the converse result strengthening the 1976 paper, proving that the Wyner-Ziv rate-distortion function is tight and that the rate loss due to lack of side information at the encoder is bounded by $0.5 lo g 2 \approx 0.5$ bits for the quadratic Gaussian case.

Estimated time

beginner: 20m
intermediate: 50m
master: 100m