NIS2337 Information Theory Notes (3): Rate-Distortion Function

Posted on 2026-04-24 Edited on 2026-09-29 Word count in article: 2.1k Reading time ≈ 8 mins.

In the discussions on the source and the channel, we typically consider distortionless communication systems, i.e., systems where the messages produced by the source are transmitted to the receiver without error. However, in practical communication systems, completely distortionless transmission is often infeasible. Therefore, we need to introduce the concept of distortion to describe the information loss in communication systems.

Nevertheless, the distortion discussed in this section differs from noise. Noise refers to random interference introduced by the channel, whereas distortion refers to the discrepancy between output and input caused by deliberate compression during encoding or transmission due to excessive message length.

NIS2337 Fundamentals of Information Theory course notes — other parts: 1. Source and Information Entropy 2. Channel and Channel Capacity 3. Rate-Distortion Function (this article) 4. Source Coding 5. Channel Coding

Additional supplementary information can be found in Beyond 2337.

Concepts and Properties

Distortion Function

Distortion. Suppose the source has symbol set and the channel output symbol set is . If the input symbol is encoded as output symbol and , then distortion exists.

Distortion function. Define the distortion function to measure the degree of distortion between the input symbol and the output symbol :

Generalized definition of the distortion function for sequences. For an input symbol sequence and an output symbol sequence , the distortion function is defined as:

Distortion matrix. All are arranged into a matrix, called the distortion matrix:

The distortion function is specified manually according to the actual situation, and its functional form can be chosen arbitrarily. Commonly used forms include: - Mean-square distortion: - Absolute-value distortion: - Relative distortion: - Hamming distortion:

Average distortion. Since the distortion function is a random variable, it is appropriate to analyze it using statistical methods. Define the average distortion as:

Average distortion for continuous random variables. Define the average distortion for continuous random variables and as:

Rate-Distortion Function

The purpose of source coding is compression, i.e., reducing the information transmission rate . However, a lower information transmission rate increases the distortion level . Hence, there exists a trade-off between the information transmission rate and the distortion level. The rate-distortion function describes the minimum information transmission rate under a given distortion level .

If we map this problem onto a channel, the rate-distortion function describes the minimum mutual information under a given average distortion level , where the distortion introduced by compression can be regarded as noise introduced into the channel. Consequently, the problem of selecting a source coding scheme can be reduced to the problem of selecting a channel. Let be a discrete source; the rate-distortion function is defined as:

For a discrete memoryless channel, .

Domain

Let the domain be .

The lower bound of is 0, which corresponds to a noiseless channel. For a discrete source, if each row of the distortion matrix contains at least one zero and each column contains at most one zero, then ; otherwise, , meaning that some symbols can be compressed and merged without introducing any distortion.

For a continuous source, its entropy is meaningful only under relative conditions. Therefore, the lower bound of is infinite, i.e., . Clearly, in practice, infinite channel capacity does not exist. Thus, transmission is possible only when some distortion is allowed (i.e., is finite).

can be infinite, in which case , meaning that no information needs to be transmitted, but this is obviously meaningless. Therefore, we choose the smallest such that .

When , , i.e., and are independent, and . Therefore,

That is, to construct corresponding to , we only need to find a that minimizes , set , and set the other ().

Convexity and Continuity

The rate-distortion function is a convex function of , i.e., for any and , we have:

Furthermore, is continuous, i.e., for any , we have .

Monotonicity

The rate-distortion function is a monotonically non-increasing function of . Proof…

	Channel Capacity	Rate-Distortion Function
Definition	Maximum information transmission rate under distortionless conditions	Minimum information transmission rate under a given distortion level
Objective	Maximize	Minimize
Constraint	satisfies channel transition probabilities	satisfies average distortion
Given conditions	Channel transition probabilities	Input distribution and distortion function
Choice parameter	Input distribution	Conditional probabilities
Object of study	Channel	Source coding

Parametric Representation Solution

Obtaining a closed-form expression for is rather difficult. Therefore, a parametric representation is commonly adopted, using the Lagrange multiplier as a parameter to derive expressions for and , thereby obtaining a numerical solution for .

Let the input sequence of the discrete source be:

and the output sequence be:

Denote , , , . Note that is not an independent variable; it is determined by .

Then the problem of solving for can be formulated as:

Introduce the Lagrange multiplier and , and construct the Lagrangian function:

Taking the partial derivative with respect to (ignoring the constant terms and , and expanding to obtain , where the constant is absorbed into ):

Rearranging yields the parametric representation of :

From the normalization condition , sum both sides of over :

Then from , substitute :

Canceling on both sides (assuming ), we obtain the system of equations for :

From , we can solve for parameterized by . Substituting into gives , and then substituting into yields the complete parametric representation of .

Substituting back into the definition of average distortion yields the average distortion parameterized by :

Substituting back into the definition of mutual information yields the information transmission rate parameterized by . Using from :

In general, a closed-form explicit expression for cannot be obtained. However, through the parametric representation, we can use as an intermediate parameter to obtain the parametric curve of –, i.e., the numerical solution of .

Furthermore, it can be shown that is exactly the slope of the curve:

The above derivation uses natural logarithms. To convert the result to bits, simply divide by .