Prerequisites & Notation

Before You Begin

This chapter requires familiarity with entropy for both discrete and continuous sources, typicality, and the lossless source coding framework from Chapter 5. Convex optimization appears prominently.

Discrete and differential entropy (Ch 1–2)(Review ch02)
Self-check: Can you compute the differential entropy $h(X)$ of a Gaussian random variable?
Mutual information $I(X;Y)$ and its properties (Ch 1)(Review ch01)
Self-check: Can you prove that $I(X;Y) = H(X) - H(X|Y)$ and that $I \geq 0$ ?
Jointly typical sequences and the covering lemma (Ch 3)(Review ch03)
Self-check: Can you state the covering lemma and explain why we need $2^{nI}$ codewords to cover the typical set?
Lossless source coding and Shannon's theorem (Ch 5)(Review ch05)
Self-check: Can you explain why $H(X)$ is the minimum rate for lossless compression?
Convex optimization: Lagrange multipliers, KKT conditions
Self-check: Can you minimize a convex function subject to inequality constraints using the KKT conditions?

Notation for This Chapter

Symbols introduced in this chapter.

Symbol	Meaning	Introduced
$\hat{\mathcal{X}}$	Reconstruction alphabet (may differ from source alphabet $\mathcal{X}$ )	s01
$d(x, \hat{x})$	Per-symbol distortion measure: $\mathcal{X} \times \hat{\mathcal{X}} \to [0, \infty)$	s01
$D$	Target average distortion level	s01
$R$	Rate-distortion function: $R = \min_{P_{\hat{X}\|X} : \mathbb{E}[d] \leq D} I(X;\hat{X})$	s02
$D(R)$	Distortion-rate function: the inverse of $R$	s02
$D_{\max}$	Maximum meaningful distortion ( $R = 0$ )	s02
$\gamma$	Reverse waterfilling level for vector Gaussian sources	s04
$U$	Auxiliary random variable in Wyner-Ziv coding	s05

← Ch 5 The Lossy Compression Problem