Cardinality bound for the finite Wyner-Ziv auxiliary

Remove all zero-probability values of $U$. For each remaining $u$, set ${\pi }_u=P_U(u)>0$, $q_u(x)=P(X=x\mathrm{\mid }U=u)$, $a_u=\mathbb{E}[d(X,g(Y,u))\mathrm{\mid }U=u]$, and $h_u=H(X\mathrm{\mid }Y,U=u)$. Because $U-X-Y$, the conditional law of $Y$ given $(X,U)$ is $P_{Y\mathrm{\mid }X}$, so $a_u$ is determined by $q_u$ and the fixed decoder map $g(\cdot ,u)$. Also, $P_X(x)={\sum }_u{\pi }_u{q}_u(x),\mathbb{E}d(X,g(Y,U))={\sum }_u{\pi }_u{a}_u,H(X\mathrm{\mid }Y,U)={\sum }_u{\pi }_u{h}_u\mathrm{.}$ These are finite sums.

Put $m=\mathrm{\mid }\mathcal{X}\mathrm{\mid }$. If there are more than $m+1$ positive weights, the vectors $v_u=(q_u(x_1),\dots ,q_u(x_m),a_u)\in {\mathbb{R}}^{m+1}$ are linearly dependent. Choose coefficients $c_u$, not all zero, with ${\sum }_u{c}_u{v}_u=0$. The first $m$ coordinates imply ${\sum }_u{c}_u=0$, so the coefficients have both signs. Choose the sign so that ${\sum }_u{c}_u{h}_u\ge 0$. Let $t={\min }_{c_u<0}{\pi }_u\mathrm{/}(-c_u)>0$ and put ${\pi }_u^{\mathrm{\prime }}={\pi }_u+t{c}_u$. Then every ${\pi }_u^{\mathrm{\prime }}\ge 0$, at least one is zero, and the source marginal and expected distortion remain unchanged, while ${\sum }_u{\pi }_u^{\mathrm{\prime }}{h}_u\ge {\sum }_u{\pi }_u{h}_u$.

Define $U^{\mathrm{\prime }}$ to have the remaining positive weights ${\pi }_u^{\mathrm{\prime }}$, conditional posterior $P(X=x\mathrm{\mid }{U}^{\mathrm{\prime }}=u)=q_u(x)$, and conditional side-information law $P_{Y\mathrm{\mid }X}$. Equivalently set $P_{XY{U}^{\mathrm{\prime }}}(x,y,u)=P_{XY}(x,y)P(U^{\mathrm{\prime }}=u\mathrm{\mid }X=x)$ with $P(U^{\mathrm{\prime }}=u\mathrm{\mid }X=x):={\pi }_u^{\mathrm{\prime }}{q}_u(x)\mathrm{/}{P}_X(x)$ for $P_X(x)>0$, and choose any row on zero-mass $x$. The source marginal is preserved by step 1.2, and ${\sum }_u{\pi }_u^{\mathrm{\prime }}{q}_u(x)=P_X(x)$ makes each conditional row sum to one. Use the same reconstruction map $g(y,u)$. The distortion is unchanged by step 1.2, and [F2] gives $I(X;U^{\mathrm{\prime }}\mathrm{\mid }Y)=H(X\mathrm{\mid }Y)-{\sum }_u{\pi }_u^{\mathrm{\prime }}{h}_u\le H(X\mathrm{\mid }Y)-{\sum }_u{\pi }_u{h}_u=I(X;U\mathrm{\mid }Y)\mathrm{.}$ At least one positive auxiliary value was removed. Repeating finitely many times leaves at most $m+1$ values and never increases the objective.

For fixed $\mathrm{\mid }\mathcal{U}\mathrm{\mid }=m+1$, the stochastic matrices $P_{U\mathrm{\mid }X}$ form a closed bounded subset of a finite-dimensional Euclidean space. Any smaller auxiliary can be embedded in this alphabet by adding zero-probability labels and assigning arbitrary decoder values to them. For each of the finitely many decoder maps $g:\mathcal{Y}\times \mathcal{U}\to \widehat{\mathcal{X}}$, the distortion constraint is closed and $I(X;U\mathrm{\mid }Y)$ is continuous by the finite entropy formulas and [F3]. Thus every nonempty feasible set is compact by [F4], and its objective minimum is attained by [F5]. Every finite auxiliary can be reduced to at most $m+1$ labels by steps 1.2–2.1 and then embedded in this fixed alphabet, so this minimum equals the original infimum.