5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.