Since rate-distortion theory underpins lossy data compression, I'm interested to learn more about it. More specifically, I want to understand why the rate-distortion function is defined such that the mutual information between a source sequence and its reconstruction is minimized. Shouldn't we maximize the mutual information to ensure that the reconstructed sequence closely mimics the original source sequence?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Let $X^n=\{X_1,X_2,...,X_n\}$ be a sequence of random source symbols. Suppose that we use a source encoder $f$ that transforms this sequence of $n$ random source symbols into a codeword $C^l=\{C_1,C_2,...,C_l\}$ of bits of length $l$, such that $C_i\in\{0,1\}$ for $i=1,2,...,l$ and: $$ f(X^n)= C^l $$ Next, given the random codeword $C^l$, suppose we use a source decoder $g$ to reconstruct the original sequence of source symbols $X^n$: $$ g(C^l)=\hat{X}^n $$ Where $\hat{X}^n=\{\hat{X}_1,\hat{X}_2,...,\hat{X}_n\}$ is the reconstruction of $X^n$. This process is illustrated in the following diagram:
Where $\mathfrak{X}^n$ is the set of all possible sequences of source symbols $X^n$ and $\hat{\mathfrak{X}}^n$ is the set of all possible reconstructions of the sequence of source symbols $\hat{X}^n$.
Our goal, and the general goal of rate-distortion theory, is to design a source encoder $f$ and source decoder $g$ to achieve the smallest rate of compression: $$ R = \frac{l}{n} \tag{1} \label{eq1} $$ Such that the per-symbol average distortion $D\left(X^n,\hat{X}^n\right)$ is at most $\delta$: $$ D\left(X^n,\hat{X}^n\right) \leq \delta $$ Where: $$ D\left(X^n,\hat{X}^n\right) = \mathbb{E}_{p(x,\hat{x})}\left[d\left(X^n,\hat{X}^n\right)\right] $$ And: $$ d\left(X^n,\hat{X}^n\right) = \frac{1}{n}\sum_{i=1}^n d\left(X_i,\hat{X}_i\right) $$ Where $d\left(X_i,\hat{X}_i\right)$ is a distortion measure between $X_i$ and $\hat{X}_i$. A distortion measure between $X_i$ and $\hat{X}_i$ is a non-negative function that can be interpreted as the cost of mis-representing $X_i$ as $\hat{X}_i$. In the case that $\mathfrak{X}^n=\hat{\mathfrak{X}}^n$, then an example of a distortion measure is the Hamming distortion (or Hamming distance): $$ d\left(X_i,\hat{X}_i\right) = \begin{cases} 0 & X_i = \hat{X}_i \\ 1 & X_i \neq \hat{X}_i \end{cases} $$ To design the source encoder $f$ and the source decoder $g$, it is helpful to make simplifying assumptions and to treat the problem slightly differently. For example, we will assume that the source is discrete and memoryless, such that $X^n$ is a sequence of independent and identically distributed discrete random variables. Therefore, it suffices to be able to reconstruct a single $\hat{X}_i$ as $X_i$ for any $i\in\{1,2,...,n\}$, which is what we will focus on. Additionally, we will replace the source encoder and decoder with a channel described by the conditional probability distribution $q(\hat{x}|x)$ as shown below:
Previously, in the case of $X^n$ and $\hat{X}^n$, our goals were to minimize the rate of compression $R$ and to limit the per-symbol average distortion to $D\left(X^n,\hat{X}^n\right) \leq \delta$. Now, in the case of $X$ and $\hat{X}$, minimizing the rate of compression $R$ intuitively corresponds to transmitting less information (bits) about $X$ through the channel shown above. To see why, notice that in equation \ref{eq1}, $l$ is the number of bits that are transmitted through the channel and $n$ is the number of source symbols, and so $R$ is measured in bits per source symbol. If we let $n=1$, then decreasing $l$ corresponds to decreasing $R$ and decreasing the number of bits that are transmitted through the channel, which is what we are after.
Transmitting less information about $X$ through the channel also corresponds to choosing a channel defined by $q(\hat{x}|x)$ that minimizes the mutual information between $X$ and $\hat{X}$, which is defined as: $$ I(X;\hat{X}) = H(\hat{X}) - H(\hat{X}|X) $$ Where: $$ \begin{align} H(\hat{X}) &= -\mathbb{E}_{p(\hat{x})}[\log{p(\hat{x})}] \\ H(\hat{X}|X) &= -\mathbb{E}_{p(\hat{x},x)}[\log{q(\hat{x}|x)}] \end{align} $$ Note that I only included this definition of the mutual information to highlight the dependence of the mutual information $I(X;\hat{X})$ on the channel $q(\hat{x}|x)$, and it is not needed to intuitively understand the rate-distortion function.
Also, we were previously interested in limiting the per-symbol average distortion, but since we are now only dealing with $X$ and $\hat{X}$, we are now interested in limiting the average distortion $D\left(X,\hat{X}\right)$ to: $$ D\left(X,\hat{X}\right) = \mathbb{E}_{p(x,\hat{x})}\left[d\left(X,\hat{X}\right)\right] \leq \delta $$ Since: $$ p(x,\hat{x}) = q(\hat{x}|x) \cdot p(x) $$ Then changing the channel $q(\hat{x}|x)$ will also change the average distortion. Intuitively, as we transmit less information about $X$ through the channel, this average distortion will increase, and it will eventually exceed the desired limit $\delta$. Therefore, what we really want to do is to choose a channel $q(\hat{x}|x)$ that minimizes the mutual information (rate of compression) between $X$ and $\hat{X}$ but also leads to an average distortion that does not exceed $\delta$. Since different values of $\delta$ will lead to different channels that can be chosen to satisfy these two goals, and therefore lead to different minimum mutual information values, then this minimum mutual information value is dependent on $\delta$. This dependence is described by the rate-distortion function $r(\delta)$: $$ r(\delta) = \min_{q(\hat{x}|x) \ : \ D\left(X,\hat{X}\right) \leq \delta} I(X;\hat{X}) $$ Once we have the optimal $q(\hat{x}|x)$, we can then work backwards and choose the source encoder $f$ and source decoder $g$ that result in the exact same conditional probability distribution $q(\hat{x}|x)$.
These EE398A Image and Video Compression lecture slides by Bernd Girod are helpful too.
It is interesting to note the similarity between the rate-distortion function and the capacity-cost function: $$ C(P) = \max_{p(x) \ : \ \mathbb{E}_{p(x)}[X^2] \leq P} I(X;Y) $$ Where $p(x)$ is the probability distribution of the source symbol $X$, $P$ is the constraint on the power of the source, and $Y$ is the output of the channel.
In the case of the capacity-cost function, we are given a fixed channel defined by the fixed conditional probability distribution $p(y|x)$, and we must choose a probability distribution $p(x)$ such that $Y$ is as dependent as possible on $X$, or $Y$ contains as much information about $X$ as possible, subject to the power constraint $\mathbb{E}_{p(x)}[X^2] \leq P$.
Conversely, in the case of the rate-distortion function, we are given a fixed source distribution $p(x)$, and we want to choose the channel $q(\hat{x}|x)$ such that we can communicate as little information as possible over the channel while not exceeding the maximum average distortion of $D\left(X,\hat{X}\right) \leq \delta$. In other words, we pick the channel that allows us to reconstruct $X$ as well as possible, but using the least amount of information.