RateDistortion

Rate-distortion theory studies the trade-off between the bitrate required to encode a source and the fidelity of its reconstruction when lossy compression is permitted. The rate, R, is the average number of bits per source symbol, and the distortion, D, is a measure of dissimilarity between the original X and its reconstruction X_hat according to a distortion function d(x, x_hat).

Formally, for a source X with distribution p(x) and reconstruction alphabet X_hat, a coding scheme of rate R can achieve distortion D if there exists a conditional distribution p(x_hat|x) such that the mutual information I(X; X_hat) ≤ R and the expected distortion E[d(X, X_hat)] ≤ D. The rate-distortion function R(D) is defined as the infimum of achievable rates for a given distortion: R(D) = min I(X; X_hat) over all p(x_hat|x) subject to E[d(X, X_hat)] ≤ D. This single-letter characterization holds for a wide range of sources in the limit of large blocklength, reflecting the fundamental limit of lossy coding.

Common distortion measures include squared error, d(x, x_hat) = (x − x_hat)^2, used for continuous-valued sources, and Hamming distortion for discrete sources. For a Gaussian source with squared-error distortion, R(D) = 0.5 log2( σ^2 / D ) for 0 < D < σ^2.

Operationally, R(D) provides the minimal achievable bitrate to ensure average distortion no larger than D, and it is nonincreasing and convex in D. The theory underpins practical lossy compression schemes for images, audio, and video, and has extensions to scenarios with side information at the decoder (Wyner–Ziv), multiple encoders, and vector quantization.