Attainment of finite-alphabet rate-distortion minima

For each $x$, choose a minimizing ${\widehat{x}}_x$ from the nonempty finite set $\widehat{\mathcal{X}}$; finite choice is available by successive selection from finitely many nonempty sets. The deterministic channel $W(\widehat{x}\mid x)={\mathbf{1}}_{\{\widehat{x}={\widehat{x}}_x\}}$ has expected distortion $D_{\min }$. Conversely, each channel row is a probability vector, so its conditional mean distortion is at least ${\min }_{\widehat{x}}d(x,\widehat{x})$; averaging against $p$ shows every channel has distortion at least $D_{\min }$. Thus feasibility is equivalent to $D\ge D_{\min }$.

For a probability vector $q$, set $H(q)=-{\sum }_i{q}_i\ln q_i$, with $0\ln 0:=0$. The scalar function $-t\ln t$ on $(0,1]$ extends continuously to zero because ${\lim }_{t\downarrow 0}t\ln t=0$; hence entropy is continuous on every finite simplex. Expanding the finite KL sum in [F1] gives $I(X;\widehat{X})=H(p)+H(q)-H(p_{X\widehat{X}})$, where $q(\widehat{x})={\sum }_{x}p(x)W(\widehat{x}\mid x)$; all terms are continuous functions of the channel coordinates.

Identify all channels with a point in $[0,1{]}^{\mathrm{\mid }\mathcal{X}\mathrm{\mid }\mathrm{\mid }\widehat{\mathcal{X}}\mathrm{\mid }}$. The row-sum equalities, nonnegativity inequalities and expected-distortion inequality define a closed set; the cube makes it bounded. When feasible it is nonempty, so [F3] makes it compact.

By [F2], division by the positive constant $\ln 2$ preserves continuity. Thus the bit mutual-information objective is continuous on the nonempty compact feasible set in step 2.1; [F4] gives a point where it attains its minimum. This proves attainment.