Rate-distortion theory asks how many bits are needed when exact reconstruction is replaced by controlled approximation.
Distortion measure
Definition. Let \(d:\mathcal X\times\widehat{\mathcal X}\to[0,\infty)\) be a distortion measure. A reproduction \(\widehat X\) is admissible at level \(D\) if \(\mathbb E d(X,\widehat X)\le D\).
Rate-distortion function
Definition. The rate-distortion function of \(X\) is \[ R(D)=\inf_{P_{\widehat X\mid X}:\,\mathbb E d(X,\widehat X)\le D}I(X;\widehat X). \]
Convexity and monotonicity
Proposition. The function \(D\mapsto R(D)\) is nonincreasing and convex on its effective domain. It is zero once \(D\) is at least the distortion achievable by a reproduction independent of \(X\).
Proof by time sharing
Proof. Nonincreasingness is immediate from enlarging the feasible set. Convexity follows by time sharing two test channels: choose one of two reproduction kernels with an independent coin, producing averaged distortion and averaged mutual information.
Operational distortion and test channels
Definition. Given source law \(P_X\) and distortion \(d(x,\widehat x)\), the rate-distortion function is \[ R(D)= \inf_{P_{\widehat X\mid X}: \mathbb Ed(X,\widehat X)\le D} I(X;\widehat X). \]
The optimizing conditional law is called a test channel. It is an information-theoretic object; an operational block code approximates its joint empirical behavior.
Basic properties
Theorem. \(R(D)\) is nonincreasing and convex in \(D\). It is zero for \[ D\ge D_{\max}= \inf_{\widehat x}\mathbb Ed(X,\widehat x), \] and, for lossless distortion on a finite alphabet, \(R(0)=H(X)\).
Proof. Enlarging the feasible set makes \(R\) nonincreasing. For test channels \(W_1,W_2\) with distortions \(D_1,D_2\), introduce independent time-sharing variable \(J\) and use \(W_J\). The resulting distortion is \(\lambda D_1+(1-\lambda)D_2\), while \(I(X;\widehat X,J)\le \lambda I_1+(1-\lambda)I_2\), proving convexity. A constant reconstruction gives \(D_{\max}\) at zero information. At zero lossless distortion, \(\widehat X=X\) surely, so information is \(H(X)\).
Binary symmetric source under Hamming distortion
Theorem. If \(X\sim\operatorname{Bernoulli}(1/2)\) and \(d(x,\widehat x)=\mathbf1(x\ne\widehat x)\), then \[ R(D)=\log2-h_2(D), \qquad0\le D\le1/2. \]
Proof. For every reconstruction, \[ I(X;\widehat X)=H(X)-H(X\mid\widehat X). \] Let \(E=\mathbf1(X\ne\widehat X)\). Since \(X\) is determined by \((\widehat X,E)\), \(H(X\mid\widehat X)\le H(E)\le h_2(D)\), giving the lower bound. Achieve it with \(\widehat X=X\oplus Z\), \(Z\sim\operatorname{Bernoulli}(D)\) independent; then \(\widehat X\) is uniform and mutual information is \(\log2-h_2(D)\).
Gaussian source under squared error
Theorem. If \(X\sim N(0,\sigma^2)\), then \[ R(D)= \left[\frac12\log\frac{\sigma^2}{D}\right]_+. \]
Proof. For any reconstruction, \[ I(X;\widehat X)=h(X)-h(X\mid\widehat X) =h(X)-h(X-\widehat X\mid\widehat X) \ge h(X)-h(X-\widehat X). \] The error has variance at most \(D\), so Gaussian extremality gives \(h(X-\widehat X)\le\tfrac12\log(2\pi eD)\). This proves the lower bound. For achievability, let \(X=\widehat X+Z\) with independent \(Z\sim N(0,D)\) and \(\widehat X\sim N(0,\sigma^2-D)\). The distortion is \(D\), and \(I(X;\widehat X)=\tfrac12\log(\sigma^2/D)\).
Shannon lower bound
Theorem. For \(X\in\mathbb R^d\) under squared error, \[ R(D)\ge h(X)-\frac d2\log\left(2\pi e\frac Dd\right), \] when \(D=\mathbb E\|X-\widehat X\|^2\).
Proof. \[ I(X;\widehat X)\ge h(X)-h(X-\widehat X). \] Among errors with trace covariance at most \(D\), isotropic Gaussian error maximizes entropy, giving the displayed upper bound on error entropy.
Inverse distortion-rate function
Definition. \[ D(R)= \inf_{P_{\widehat X\mid X}:I(X;\widehat X)\le R} \mathbb Ed(X,\widehat X). \] It is the generalized inverse of \(R(D)\) at continuity points and is nonincreasing and convex in an appropriate time-sharing sense.
Successive refinement
A source is successively refinable at distortions \(D_1>D_2\) if a coarse description at rate \(R(D_1)\) can be augmented to total rate \(R(D_2)\) without loss relative to separate optimal codes. Gaussian sources under squared error and symmetric discrete sources under Hamming distortion have this property; arbitrary sources need not.
Remote source coding
If the encoder observes \(Y\) correlated with hidden source \(X\), the indirect rate-distortion function is \[ \inf_{P_{\widehat X\mid Y}: \mathbb Ed(X,\widehat X)\le D} I(Y;\widehat X). \] This separates estimation from compression only in special models; generally the optimal representation balances both jointly.