Rate-Distortion Theory and the Shape of Lossy Compression

Lossless coding has a single number attached to a source: the entropy rate, below which no code can go. Lossy coding has a function. For each acceptable level of distortion there is a minimum rate, and the function that maps one to the other is the rate-distortion function. Everything about lossy compression, from quantizer design to transform choice to the reason JPEG has a quality parameter, follows from the shape of that curve and from how far a practical scheme sits above it.

Defining distortion and the function

A distortion measure $d(x, \hat{x})$ assigns a nonnegative cost to reproducing source symbol $x$ as $\hat{x}$. The squared-error measure $(x - \hat{x})^2$ is the common choice for continuous sources because it is analytically tractable and because it matches what transform coders optimize; for perceptual data it is a poor proxy, which is one reason image and audio codecs use weighted or perceptual measures instead.

For a source with distribution $p(x)$ and a conditional reproduction distribution $p(\hat{x} \mid x)$, the expected distortion is $\mathbb{E}[d(X, \hat{X})]$ and the mutual information is $I(X; \hat{X})$. The rate-distortion function is the smallest mutual information achievable at distortion $D$ or below:

$$R(D) = \min_{p(\hat{x} \mid x) : \mathbb{E}, d(X, \hat{X}) \le D} I(X; \hat{X})$$

The minimization is over reproduction channels, not over codes. The coding theorem then states that any rate above $R(D)$ admits a code with distortion at most $D$, and no code at rate below $R(D)$ can achieve it. The structure is the same as the channel coding theorem with the roles of rate and fidelity exchanged, and the proof techniques are the same: random coding for the direct part, a converse using the data processing inequality.

Three properties of $R(D)$ hold for any source and any reasonable distortion measure. It is nonincreasing in $D$, because a larger distortion budget cannot require more rate. It is convex, which is the property that makes the minimization tractable: the program above is a convex optimization over the reproduction conditional distribution. And it reaches zero at $D_{\max}$, the distortion achieved by the best constant reproduction, which for squared error is the variance of the source.

The Gaussian case, solved exactly

For a memoryless Gaussian source with variance $\sigma^2$ and squared-error distortion, the minimization has a closed form:

$$R(D) = \begin{cases} \tfrac{1}{2}\log_2 \dfrac{\sigma^2}{D} & 0 \le D \le \sigma^2 \ 0 & D > \sigma^2 \end{cases}$$

The achievability argument is instructive. Take the reproduction $\hat{X}$ to be Gaussian with variance $\sigma^2 - D$ and set $X = \hat{X} + Z$ with $Z$ Gaussian of variance $D$, independent of $\hat{X}$. The error $X - \hat{X} = Z$ then has exactly variance $D$, and $I(X;\hat{X}) = h(\hat{X}) - h(\hat{X} \mid X) = \tfrac12 \log_2(2\pi e(\sigma^2 - D)) - \tfrac12\log_2(2\pi e D)$, which simplifies to the expression above. The converse uses the entropy power inequality to show no other reproduction distribution can do better.

Read the formula as a budget. Every halving of the distortion costs half a bit per sample, regardless of the absolute distortion level. To reduce distortion by a factor of 100, a rate increase of about 3.3 bits per sample is required. That logarithmic relationship is why quality settings in lossy codecs are usually expressed on a logarithmic scale and why the last few decibels of quality are disproportionately expensive.

For a source with a non-Gaussian distribution, the Gaussian formula is an upper bound on $R(D)$ at the same variance for small $D$, where the entropy power inequality gives $R(D) \le \tfrac12 \log_2(\sigma^2/D)$ for any source of variance $\sigma^2$. A Gaussian source is the hardest to compress in that regime, because it has the largest differential entropy for a given variance. The bound is asymptotic and need not hold at every distortion level: a source with a constant offset and narrow support can require a positive rate at a distortion level that the Gaussian formula already reports as zero, since the Gaussian curve only vanishes at $D = \sigma^2$. Real sources with structure do better in the small-distortion regime, and the difference is the gain that a good model or transform can capture.

Transform coding and the reverse water-filling result

A block of $n$ samples passed through an orthogonal transform produces $n$ coefficients whose variances differ. If the transform decorrelates the block, the coefficients can be coded independently with a total squared error equal to the sum of the per-coefficient errors, since orthogonality preserves the $L_2$ norm.

The optimal allocation of distortion across coefficients with variances $\sigma_i^2$ is reverse water-filling: choose a threshold $\theta$, set the distortion of each coefficient to $\min(\theta, \sigma_i^2)$, and spend no bits at all on coefficients whose variance is below the threshold. The resulting rate is

$$R = \sum_{i:, \sigma_i^2 > \theta} \tfrac{1}{2} \log_2 \frac{\sigma_i^2}{\theta}$$

The name comes from the shape: the distortion is poured into the coefficients like water into a vessel with unequal bottoms, filling the high-variance coefficients up to the common level and leaving the low-variance ones dry. Coefficients below the threshold are set to zero, which is the theoretical justification for the quantization matrices in JPEG and the zeroing of high-frequency bands. The threshold is the parameter that a quality setting adjusts, and the rate is what it costs.

This is also the argument for the discrete cosine transform over the discrete Fourier transform in image coding. Both are orthogonal, but the DCT’s even symmetry at block boundaries packs more of the energy into a few coefficients for typical image statistics, so the variance profile is steeper and more coefficients fall below the threshold for the same total error. The gain is not a theorem about the DCT; it is a statement about the match between the transform’s basis and the covariance of natural images, which is empirical and not universal.

Why vector quantization beats scalar quantization

A scalar quantizer maps each sample independently to one of $2^{R}$ levels, so $R$ bits per sample. A vector quantizer spends the same total budget on a block of $k$ samples and maps the block to one of $2^{kR}$ codewords in $\mathbb{R}^k$. For the same rate, the vector quantizer can do strictly better, and the reason is geometric.

Consider two independent Gaussian samples, each quantized to one bit. A scalar quantizer splits each axis at zero, producing four rectangular cells in a grid, and each cell is represented by a single point at its centre. The two-bit rate buys four codewords; the same four codewords arranged as a rotated lattice, such as a hexagonal or checkerboard pattern, cover the same probability mass with less average squared error. Even at this dimension the optimal quantizer is better than the product of two scalar quantizers, though by a small margin; the margin grows with dimension, and the growth is what makes vector quantization worth its cost.

The asymptotic result is the space-filling gain. In $k$ dimensions, the best lattice quantizer has normalized second moment approaching $1/(2\pi e)$ as $k$ grows, and the resulting rate exceeds $R(D)$ by a constant. The constant for scalar quantization is about 0.25 bits per sample for a Gaussian source; for high-dimensional optimal vector quantization it vanishes. Practical coders cannot use unbounded dimension because the codebook size grows exponentially, so the search cost and storage dominate.

The compromise used everywhere is a structured codebook. Lattice quantizers, trellis-coded quantization, and the residual structure inside a transform coder all restrict the codebook to a form that can be searched in polynomial time while retaining most of the space-filling gain. Entropy-constrained quantization, which minimizes rate plus a Lagrange multiplier times distortion, is the formulation that makes this practical: instead of fixing the number of levels, it fixes the trade-off and lets the quantizer choose levels and their entropies jointly.

How far practical coders sit from the bound

A working lossy codec differs from $R(D)$ by several additive terms, and identifying them is useful when reasoning about where the remaining gains are.

Quantizer gap. As above, about 0.25 bits per sample for scalar quantization of a Gaussian source, measured as the extra rate needed to reach a given distortion compared with the rate-distortion function. Vector quantization and entropy-constrained design reduce it; a fixed-length code over a scalar quantizer without entropy coding enlarges it.

Model gap. The codec’s probability model over quantized coefficients is not the true distribution. An adaptive arithmetic coder over a context model narrows this, but the residual is the Kullback–Leibler divergence between model and truth, exactly as in the lossless case.

Transform gap. A fixed block transform is not the Karhunen–Loève transform of the source’s covariance, so the coefficients remain correlated and the variance profile is shallower than optimal. Larger blocks reduce the gap and increase the cost of transmitting side information.

Non-Gaussianity and perceptual weighting. Squared error is the wrong measure for images and audio, and a codec that optimizes it will spend bits on errors that are invisible while missing errors that are not. The rate-distortion curve for a perceptual measure is different from the curve for squared error, and comparing a codec’s measured rate against the squared-error bound is not a meaningful test of its efficiency.

The theoretical value of $R(D)$ is therefore the same as the value of channel capacity: it identifies what is fundamental and what is implementation loss, and it explains which resource is binding. It does not describe any particular encoder’s output size.

Limits of the formulation

The definition assumes a known source distribution and a stationary source. For a source whose statistics vary, the relevant quantity is an average over the source’s states, and a single code designed for the average spends its rate in the wrong proportion in each individual state. Switched or multi-mode codecs address this by selecting among several models per block, which converts the problem into one of side-information cost.

The distortion measure must be a single scalar summary. Multi-objective problems, whether the axes are rate, distortion, and complexity or several regional distortion measures, do not have a single $R(D)$ curve, and the achievable region is a set rather than a function. The extension to multiple descriptions, where several receivers with different channel qualities are served by one encoded stream, produces a rate-distortion region rather than a curve, and its characterization is substantially harder.

Finally, the theorem is asymptotic in block length, just as the channel coding theorem is. The finite-block-length penalty appears as a term proportional to the square root of the block’s inverse length times the source dispersion, and for the small blocks used in low-latency codecs that term is not negligible. A codec operating close to $R(D)$ at a block length of a few hundred samples pays a visible rate premium for the short block, which is the same trade that Mutual Information and the Capacity of a Noisy Channel describes on the channel side.