Rate-Distortion Function

The least rate for a tolerated average distortion: R(D) = min I(X; X-hat).

The idea

The rate-distortion function gives the smallest rate, in bits per symbol, at which a source can be compressed when the reproduction is allowed a specified amount of error — the fundamental limit of lossy compression.

Lossless coding cannot go below the entropy $H(X)$ bits per symbol. Allowing an approximate reproduction $\hat{X}$ lowers the cost, and to state by how much we fix a distortion measure $d(x, \hat{x}) \ge 0$, the penalty for reproducing $x$ as $\hat{x}$, and a budget $D$ on its average. A test channel $p(\hat{x} \mid x)$ is a conditional distribution describing how a reproduction is generated from the source.

Definition (Rate-distortion function).

The rate-distortion function of a source $X$ under the distortion measure $d$ is $R(D) = \min_{p(\hat{x} \mid x)\ :\ \mathbb{E}[d(X, \hat{X})] \le D} I(X; \hat{X}),$ the least mutual information between source and reproduction over all test channels whose expected distortion meets the budget $D$.

Theorem (Lossy source coding theorem).

The smallest rate, in bits per symbol, at which the source can be encoded so that the reproduction has expected distortion at most $D$ is $R(D)$.

Enlarging the budget $D$ enlarges the set of admissible test channels, so $R(D)$ never rises as $D$ grows. It is the lossy counterpart of the source coding theorem, with the single number $H(X)$ replaced by a curve: starting from $R(0) = H(X)$, the graph of $R(D)$ falls as the budget grows and reaches $0$ at the smallest budget $D_{\max}$ that a constant reproduction already meets.

Ways to work on it

• Walkthrough. Definition of R(D), its monotonicity, and the binary source.
• Practice. Evaluate the Gaussian rate-distortion function.
• Hardest. Trace the binary source's R(D) curve and invert it.

Not sure where to start? Take the ten-question placement test.