Let $(X_t)_{t\in T}$ be a stationary random process with known and fixed law $P_X$ describing a dynamic source. This source is to be encoded real-time by an encoder $e$ into an encoded message $E_t$ and passed through a noisy channel $c$, which gives a channel output $Y_t$. This is then decoded, again real-time, by a decoder $d$, giving a reconstruction $\hat X_t$ of the original message $X_t$. There is noiseless feedback from the channel back to the encoder, i.e. the encoder can use the history of output, encoded in the $\sigma$-field $\mathcal{F}^Y_t$ of the channel to better encode the message coming from the source.

We fix a distortion function $\text{dist}$ and define

$$R(D)=\inf\big\{ \mathcal{I}(X;Y)\; | \; e,d,c \text{ such that } \mathbb{E}[\text{dist}(X_t,\hat X_t)]\leq D \big\},$$

called the rate distortion function of the source $X$. Here $\mathcal{I}(X;Y)$ denotes the mutual information rate between the processes. The rate distortion function is a property of the source only (given a distortion measure). We say that a triple $e,d,c$ achieves the rate distortion function of the source if $\mathcal{I}(X;\hat X)$ for that system is equal to $R(D)$ while $\mathbb{E}[\text{dist}(X_t,\hat X_t)]\leq D$.

In this setting, here is a natural conjecture:

Let a channel $c$ with a capacity $C\geq R(D)$ be given and $\text{dist}$ be a Bregman loss function. There is a deterministic function $f$ such that the rate distortion function is achieved by an encoder of the form $E_t=e(X_t,Y_0^t,t)=f(X_t-\hat X_t)$, where $\hat X_t=\mathbb{E}[X_t|\mathcal{F}^Y_t]$.

The Bregman condition ensures that irrespective of the encoder and channel, the optimal decoder is given by the conditional expectation.

Is this known to be true/false?

It is trivially true for a discrete-time, i.i.d. source. Also, by [1], the capacity per unit time of a continuous-time white Gaussian channel $Y_t=\int_0^tE_s ds+W_t$ with average-power constraint $\mathbb{E}[E_t^2]\leq P_0$ is $C=\frac12 P_0$. If the source $X_t$ is an Ornstein-Uhlenbeck process $dX_t=-\theta X_t dt+\sigma dB_t$, by [2] its rate distortion function for mean-squared error loss function is given by $R(D)=\frac{\sigma^2}{2D}-\theta$. So in this case, if $C\geq R(D)$, it can be shown that an encoder of the form $E_t=\alpha(X_t-\hat X_t)$ with

$$\alpha=\frac{\sqrt{\sigma^2-2\theta D}}{D}$$

achieves distortion $D$ and rate $R(D)$.

Does this generalize to nonlinear/non-Gaussian channels/sources or are there some simple counterexamples?

[1] Ihara, S. (1974). Coding theory in white Gaussian channel with feedback. Journal of Multivariate Analysis, 4, 74–87.

[2] Bucy, R. S. (1982). Distortion Rate Theory and Filtering. IEEE Transactions on Information Theory, 28(2), 336–340.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.