Convexity, monotonicity, and continuity of finite Wyner-Ziv rate

For any map $h:\mathcal{Y}\to \widehat{\mathcal{X}}$ and every $(x,y)$, $d(x,h(y))\ge {\min }_{\widehat{x}}d(x,\widehat{x})$; minimizing over the finite set of maps gives $D_{\min }\le D_{\max }$. The feasible test-channel sets are nested as $D$ increases, so their infima are nonincreasing. For $s>0$, $\ln s\le s-1$ because $s-1-\ln s$ has derivative $1-1\mathrm{/}s$ and minimum $0$ at $s=1$. Thus, for pmfs $p,q$, either $D(p\mathrm{\parallel }q)=+\mathrm{\infty }$ when $p_i>0=q_i$ for some $i$, or $D(p\mathrm{\parallel }q)\ge {\sum }_{i:p_i>0}(p_i-q_i)=1-{\sum }_{i:p_i>0}{q}_i\ge 0$. By [F1] and [F4], each conditional mutual information is a positive weighted sum of such divergences, so every feasible objective is nonnegative. A constant auxiliary $U$ and a minimizing map $h$ at $D_{\max }$ have objective zero and distortion $D_{\max }$, proving $R_{\mathrm{W}\mathrm{Z}}(D)=0$ for $D\ge D_{\max }$.

Let $D_1,D_2\ge D_{\min }$ and $0\le \lambda \le 1$. By [F2], choose minimizing channels $(U_1,g_1)$ and $(U_2,g_2)$, whose distortions $d_1,d_2$ satisfy $d_j\le D_j$. Let an independent finite $Q$ select branch 1 with probability $\lambda$, set $U=(Q,U_Q)$, and use $g(Y,U)=g_Q(Y,U_Q)$. Then $U-X-Y$, the distortion $\lambda d_1+(1-\lambda )d_2$ is at most $\lambda D_1+(1-\lambda )D_2$, and the finite conditional chain rule gives $I(X;U\mathrm{\mid }Y)=I(X;Q\mathrm{\mid }Y)+I(X;U_Q\mathrm{\mid }Y,Q)=\lambda R_{\mathrm{W}\mathrm{Z}}(D_1)+(1-\lambda )R_{\mathrm{W}\mathrm{Z}}(D_2)$ because $Q$ is independent of $(X,Y)$. Applying [F2] to reduce $U$ if necessary proves convexity.

On the interior of $[D_{\min },D_{\max }]$, write $s(a,b)=(R_{\mathrm{W}\mathrm{Z}}(b)-R_{\mathrm{W}\mathrm{Z}}(a))\mathrm{/}(b-a)$. Convexity implies $s(a,b)\le s(b,c)$ whenever $a<b<c$, by writing $b$ as a convex combination of $a,c$. For $D_{-}<z<D$, this gives $s(D_{-},z)\le s(z,D)$, hence $R_{\mathrm{W}\mathrm{Z}}(z)\le \frac{D-z}{D-D_{-}}{R}_{\mathrm{W}\mathrm{Z}}(D_{-})+\frac{z-D_{-}}{D-D_{-}}{R}_{\mathrm{W}\mathrm{Z}}(D)$; the right side tends to $R_{\mathrm{W}\mathrm{Z}}(D)$ as $z\uparrow D$, while monotonicity gives $R_{\mathrm{W}\mathrm{Z}}(z)\ge R_{\mathrm{W}\mathrm{Z}}(D)$. For $D<z<D_{+}$, the inequalities $s(D_{-},D)\le s(D,z)\le s(z,D_{+})$ bound $R_{\mathrm{W}\mathrm{Z}}(z)$ between two linear interpolations that both tend to $R_{\mathrm{W}\mathrm{Z}}(D)$ as $z\downarrow D$. This proves continuity at $D$. For right continuity at $D_{\min }<D_{\max }$, let $r<R_{\mathrm{W}\mathrm{Z}}(D_{\min })$ and let $K_j$ be the set of channels with $\mathrm{\mid }\mathcal{U}\mathrm{\mid }=\mathrm{\mid }\mathcal{X}\mathrm{\mid }+1$ and decoder maps whose distortion is at most $D_{\min }+1\mathrm{/}j$ and whose objective is at most $r$. The union of the finitely many channel simplexes over decoder maps is compact by [F5]: each simplex is closed and bounded in a finite-dimensional Euclidean space, and a finite union of compact sets is compact. For $0<t\le 1$, $0\le -t\ln t=t\ln (1\mathrm{/}t)=t{\int }_1^{1\mathrm{/}t}\frac{du}{u}\le t{\int }_1^{1\mathrm{/}t}\frac{du}{\sqrt{u}}\le 2\sqrt{t}$, so $-t\ln t$ extends continuously to $0$; hence each finite entropy sum is continuous in its probability coordinates. By [F3], $I(X;U\mathrm{\mid }Y)=H(X,Y)+H(U,Y)-H(Y)-H(X,U,Y)$. Each joint law in this expression depends linearly on the channel entries, and its entropy is continuous by the preceding limit, so the objective is continuous; for each fixed decoder map the expected distortion is also a finite linear function of the channel entries. Therefore each $K_j$ is closed. If every $K_j$ were nonempty, they would be nested closed subsets of this compact space with the finite intersection property: if their total intersection were empty, their open complements would cover the compact space and a finite subcover would force one $K_j$ empty. Thus their intersection is nonempty, yielding a channel feasible at $D_{\min }$ with objective at most $r$, contrary to $r<R_{\mathrm{W}\mathrm{Z}}(D_{\min })$. It follows that $R_{\mathrm{W}\mathrm{Z}}(D)>r$ on some right neighborhood of $D_{\min }$; since $R_{\mathrm{W}\mathrm{Z}}(D)\le R_{\mathrm{W}\mathrm{Z}}(D_{\min })$ by monotonicity, right continuity follows.

For $D_{\min }\le D\le D_{\max }$ with $D_{\min }<D_{\max }$, time-share a minimum-distortion channel at $D_{\min }$ with the zero-rate channel at $D_{\max }$. This gives $R_{\mathrm{W}\mathrm{Z}}(D)\le \frac{D_{\max }-D}{D_{\max }-D_{\min }}{R}_{\mathrm{W}\mathrm{Z}}(D_{\min })$, so $R_{\mathrm{W}\mathrm{Z}}(D)\to 0$ as $D\uparrow D_{\max }$. Nonnegativity and the zero-rate branch in step 1.1 prove continuity there. If $D_{\min }=D_{\max }$, the zero-rate channel already attains the minimum distortion, so the feasible function is identically zero. For $D<D_{\min }$, every test channel has distortion at least $D_{\min }$, so the feasible set is empty and $R_{\mathrm{W}\mathrm{Z}}(D)=+\mathrm{\infty }$ by Definition; for $D\ge D_{\max }$, step 1.1 gives zero.