Finite-alphabet lossy source coding with decoder-only side information

Let $(X_t,Y_t{)}_{t\ge 1}$ be an IID pair with joint pmf $P_{XY}$ on finite nonempty alphabets $\mathcal{X}\times \mathcal{Y}$, as the $k=2$ instance of Finite-alphabet IID multisource. Let $\widehat{\mathcal{X}}$ be finite nonempty and let $d:\mathcal{X}\times \widehat{\mathcal{X}}\to [0,d_{\max }]$ be the finite bounded single-letter distortion from Single-letter and block distortion. For $x^n=(x_1,\dots ,x_n)$ and ${\widehat{x}}^n=({\widehat{x}}_1,\dots ,{\widehat{x}}_n)$, define

$d_n(x^n,{\widehat{x}}^n):=\frac{1}{n}{\sum }_{t=1}^{n}d(x_t,{\widehat{x}}_t)\mathrm{.}$

A length-$n$, $M$-message Wyner-Ziv code consists of a deterministic encoder $f_n:{\mathcal{X}}^n\to [M]$ and deterministic decoder $g_n:[M]\times {\mathcal{Y}}^n\to {\widehat{\mathcal{X}}}^n$. The encoder observes only $X^n$; the decoder observes both the message and $Y^n$. Its rate is $n^{-1}\ln M$ nats per source symbol, and its expected distortion is $\mathbb{E}[d_n(X^n,g_n(f_n(X^n),Y^n))]$.

A pair $(R,D)$ is operationally achievable if there are increasing blocklengths $n_j\to \mathrm{\infty }$ and such codes with ${\mathrm{lim\hspace{0.17em}sup}}_j{n}_j^{-1}\ln M_j\le R$ and ${\mathrm{lim\hspace{0.17em}sup}}_j\mathbb{E}[d_{n_j}]\le D$. Define $R_{\mathrm{W}\mathrm{Z}}^{\mathrm{o}\mathrm{p}}(D)$ as the infimum of achievable rates.

For a finite auxiliary alphabet $\mathcal{U}$, a test channel is a stochastic kernel $P_{U\mathrm{\mid }X}$ together with a deterministic map $g:\mathcal{Y}\times \mathcal{U}\to \widehat{\mathcal{X}}$, under the joint law $P_{XYU}=P_{XY}{P}_{U\mathrm{\mid }X}$. It has $U-X-Y$, expected distortion $\mathbb{E}[d(X,g(Y,U))]$, and conditional mutual information $I(X;U\mathrm{\mid }Y)$ from Finite conditional mutual information. Define the single-letter candidate $R_{\mathrm{W}\mathrm{Z}}(D):={\inf }_{\begin{array}{c}\mathcal{U}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e},P_{U\mathrm{\mid }X},g\\ \mathbb{E}[d(X,g(Y,U))]\le D\end{array}}I(X;U\mathrm{\mid }Y),$ with value $+\mathrm{\infty }$ if the feasible set is empty. This definition alone makes no operational equality claim; the following theorem proves it and the cardinality lemma makes the finite minimum explicit.

Every reproduction has distortion at least $D_{\min }:=\mathbb{E}[{\min }_{\widehat{x}\in \widehat{\mathcal{X}}}d(X,\widehat{x})]$, and the finite alphabet allows $U=X$ with a fixed pointwise minimizer to attain it. The zero-rate distortion is $D_{\max }:={\min }_{h:\mathcal{Y}\to \widehat{\mathcal{X}}}\mathbb{E}[d(X,h(Y))]$; there are finitely many maps $h$, and a constant auxiliary with a minimizing $h$ attains it. The block code has only the encoder and decoder interfaces displayed in the statement; there is no encoder-side observation of $Y^n$.