Rate Distortion and Lossy Source Coding — Examples

Here $p_0=1\mathrm{/}4$. Substitution in [F1] gives $R(0)=h_2(1\mathrm{/}4)-h_2(0)=h_2(1\mathrm{/}4)$ and $R(1\mathrm{/}8)=h_2(1\mathrm{/}4)-h_2(1\mathrm{/}8)$. At $D=1\mathrm{/}4$, the threshold branch gives zero; the constant reconstruction zero has distortion $P(X=1)=1\mathrm{/}4$ and carries no information.

For $D\in \{0,1\mathrm{/}8\}$, put $q=(1\mathrm{/}4-D)\mathrm{/}(1-2D)$, which equals $1\mathrm{/}4$ or $1\mathrm{/}6$, respectively. Construct independent $Y\sim \mathrm{Bernoulli}(q)$ and $E\sim \mathrm{Bernoulli}(D)$ on their finite product space and set $X=Y\oplus E$. Then $P(X=1)=D+q(1-2D)=1\mathrm{/}4$ and $P(X\mathrm{\ne }Y)=D$. Given either value of $Y$, the two conditional source masses are $D$ and $1-D$ in some order. Thus the finite joint-information sum is ${\sum }_{x,y}P(X=x,Y=y){\log }_2(P(X=x\mid Y=y)\mathrm{/}P(X=x))=h_2(1\mathrm{/}4)-h_2(D)$, with zero terms omitted. These channels attain the rates in step 1.1; in particular the backward test channel at $D=1\mathrm{/}8$ has reproduction mass $P(Y=1)=1\mathrm{/}6$.

The function $h_2$ is continuous on $[0,1]$ under $0{\log }_{2}0=0$, so ${\lim }_{D\uparrow 1\mathrm{/}4}[h_2(1\mathrm{/}4)-h_2(D)]=0=R(1\mathrm{/}4)$. This verifies the stated endpoint continuity.

The constant choice $Y=0$ has expected distortion $\mathbb{E}{X}^2={\sigma }^2\le D$. Since $Y$ is constant, $P_{XY}=P_X\otimes {\delta }_0=P_X\otimes P_Y$, so [F2] gives mutual information zero. By [F3], zero is the minimum rate; hence this reconstruction is optimal.

The singleton $\{0\}$ has Lebesgue measure zero but ${\delta }_0(\{0\})=1$. Thus ${\delta }_0$ is not absolutely continuous with respect to Lebesgue measure and, by [F4], cannot have a Lebesgue density.

Since $1<\theta <4$, the water-level equation is $\min (4,\theta )+\min (1,\theta )=\theta +1=5\mathrm{/}2$, so $\theta =3\mathrm{/}2$. The allocated distortions are $(\min (4,3\mathrm{/}2),\min (1,3\mathrm{/}2))=(3\mathrm{/}2,1)$. By [F1]–[F2], $R(5\mathrm{/}2)=\frac{1}{2}({\log }_2\frac{4}{3\mathrm{/}2}+{\log }_2^{+}\frac{1}{3\mathrm{/}2})=\frac{1}{2}{\log }_2\frac{8}{3}\mathrm{.}$

Put $a=\sqrt{5\mathrm{/}2}$ and $b=\sqrt{3\mathrm{/}2}$. Choose independent standard normals $U,V,X_2$ by [F5], and set $X_1=aU+bV$, $Y_1=aU$, $Y_2=0$. The matrix with rows $(a,b)\mathrm{/}2$ and $(b,-a)\mathrm{/}2$ is orthogonal, so [F4] gives $X_1\sim N(0,4)$, independently of $X_2$. The errors are $bV$ and $X_2$, with total mean square $b^2+1=5\mathrm{/}2$.

Write $f_s(t)=(2\pi s{)}^{-1\mathrm{/}2}\exp (-t^2\mathrm{/}(2s))$ for the $N(0,s)$ density. By [F4]–[F6], $(X_1,Y_1)$ has density $f_{a^2}(y)f_{b^2}(x-y)$. Relative to Lebesgue measure in $(x_1,x_2,y_1)$ times the point mass at $y_2=0$, the joint law and product of the marginals therefore have respective positive densities $f_{a^2}(y_1)f_{b^2}(x_1-y_1)f_1(x_2)$ and $f_4(x_1)f_1(x_2)f_{a^2}(y_1)$. Their log ratio is $\frac{1}{2}\ln \frac{4}{b^2}-\frac{(x_1-y_1{)}^2}{2b^2}+\frac{x_1^2}{8}\mathrm{.}$ It is integrable since both quadratic terms have finite expectations. By [F3] and step 1.2 its joint expectation is $\frac{1}{2}\ln (8\mathrm{/}3)-\frac{1}{2}+\frac{1}{2}=\frac{1}{2}\ln (8\mathrm{/}3)$ nats. Dividing by $\ln 2$ yields the rate in step 1.1, proving attainment without assuming a Lebesgue density for the constant reconstruction coordinate.