Rate–distortion theory

Rate distortion theory is the branch of information theory addressing the problem of determining the minimal amount of entropy (or information) R that should be communicated over a channel such that the source (input signal) can be reconstructed at the receiver (output signal) with given distortion D. As such, rate distortion theory gives theoretical bounds for how much compression can be achieved using lossy data compression methods. Many of the existing audio, speech, image, and video compression techniques have transforms, quantization, and bit rate allocation procedures that capitalize on the general shape of rate-distortion functions.

Rate distortion theory was created by Claude Shannon in his founding work on information theory.

Introduction

In rate distortion theory, the rate is usually understood as the number of bits per data sample to be stored or transmitted. The notion of distortion is a subject of on-going discussion. In the most simple case (which is actually used in most cases), the distortion is defined as the variance of the difference between input and output signal (i.e., the mean-squared error of the difference). However, since we know that most lossy compression techniques operate on data that will be perceived by humans (listen to music, watch pictures and video) the distortion measure preferebly should include some aspects of human perception. In audio compression perceptual models, and therefore perceptual distortion measures, are well developed and routinely used in compression techniques such as mp3, but often not easy to include in rate-distortion theory. In image and video compression, the human perception models are less well developed and inclusion is mostly limited to the JPEG and MPEG weighing (quantization, normalization) matrix.

Rate-Distortion Functions

The functions that relate the rate and distortion are found as the solution of the following minimization problem:

min_Q_{Y|X}(y|x) I_Q(Y|X)

Unfortunately, solving this minimization problem can be done only for few cases, of which the following two are the most well known ones. However, although exact solutions are only available in a few cases, measured rate-distortion functions in real life tend to have very similar forms.

Memoryless (Independent) Gaussian Source

to be written

Gaussian source with memory

to be written