Blahut–Arimoto certified gap and termination

For every reproduction pmf $q$, including boundary points of the simplex, define $G(W,q):={\sum }_i{p}_{i}D(W(\cdot \mathrm{\mid }i)\mathrm{\parallel }q)+\beta \mathbb{E}d$, where a row divergence is $+\mathrm{\infty }$ if that row puts positive mass outside the support of $q$. Since each $p_i>0$, $G(W,q)$ is finite only when every row is supported on $\{j:q(j)>0\}$. Also $Z_i(q)>0$ for every pmf $q$, because $e^{-\beta d_{ij}}>0$ and $q$ has total mass one. Define $W_q(j\mathrm{\mid }i)=q(j)e^{-\beta d_{ij}}\mathrm{/}{Z}_i(q)$, which is zero off that support. For every supported row, expansion of finite KL sums gives $D(W(\cdot \mathrm{\mid }i)\mathrm{\parallel }q)+\beta {\sum }_{j}W(j\mathrm{\mid }i)d_{ij}=D(W(\cdot \mathrm{\mid }i)\mathrm{\parallel }{W}_q(\cdot \mathrm{\mid }i))-\ln Z_i(q)\mathrm{.}$ Nonnegativity [F3] shows that $W_q$ minimizes each row; unsupported rows have infinite objective and cannot improve it. Therefore $F(q):={\min }_{W}G(W,q)=-{\sum }_i{p}_i\ln Z_i(q)$ on the closed simplex. If $q_W$ is the output law of $W$, expansion on the common support gives $G(W,q)=L_{\beta }(W)+D(q_W\mathrm{\parallel }q)$ when $q_W$ is supported on $q$; otherwise both sides are $+\mathrm{\infty }$.

Fix an integer $t$. The recurrence through $t$ is a finite expression DAG with positive exact divisors and logarithm arguments, since every iterate has full support. The algorithm uses mantissa precision $r^2$, exponent bounds $-r,r$, and truncation $N=r$. Uniformly for each endpoint $x$ in a fixed bounded input interval, the evaluator in [F6] uses $s=r+2$ squarings after reducing to $u=x\mathrm{/}{2}^s$. On a fixed bounded neighborhood of $x$, [F7] bounds the initial series error by $C^{r+1}{2}^{-s(r+1)}\mathrm{/}(r+1)!$ for some fixed $C\ge 1$, and the endpoint rounding error by $O(2^{-r^2})$. The exact intermediate exponentials are uniformly bounded; on a fixed larger bounded interval, squaring is Lipschitz with some fixed constant $A>1$. Thus the total endpoint error after $s$ rounded squarings is at most $A^{r+2}$ times the initial error plus $O(A^{r+2}{2}^{-r^2})$, which tends to zero. The exact exponential is Lipschitz on that interval, so a shrinking input interval has a shrinking output enclosure. This bound also ensures the rounded intermediates remain in that larger interval for all sufficiently large $r$. Logarithm range reduction on a fixed positive compact interval uses only finitely many bins; its series tails tend to zero, and its endpoint operations are continuous there. Rational input rounding likewise converges by [F7]. Applying these bounds successively to the finite recurrence DAG shows every requested enclosure width tends to zero. All exact positive divisors and logarithm arguments are eventually separated from zero, and the expanding exponent range eventually avoids overflow. The finite maximum forming $G_t$ preserves convergence, so its logarithm enclosure also shrinks to $\ln {\gamma }_t$. Soundness follows from [F6]. Hence each fixed-$t$ precision loop terminates with the required width.

The channel simplex is closed and bounded in finite-dimensional Euclidean space, hence compact by [F4]. The finite mutual-information objective is continuous by its entropy expression and continuity of $-u\ln u$ at zero; distortion is linear. Thus [F5] gives a minimizer $W^{\ast }$. Put $q^{\ast }=q_{W^{\ast }}$, $P^{\ast }(i,j)=p_i{W}^{\ast }(j\mathrm{\mid }i)$. Step 1.1 gives $G(W,q)\ge L_{\beta }(W)\ge L_{\beta }^{\ast }$ for every $W,q$, while $G(W^{\ast },q^{\ast })=L_{\beta }^{\ast }$ because $q^{\ast }$ is the output marginal of $W^{\ast }$. Therefore $F(q^{\ast })=L_{\beta }^{\ast }$ and $q^{\ast }$ minimizes the boundary-extended $F$.

For each iterate set $P_t(i,j)=p_i{W}_t(j\mathrm{\mid }i)$. The identities in step 1.1 give $F(q_t)=L_t+D(q_{t+1}\mathrm{\parallel }{q}_t),F(q_{t+1})\le G(W_t,q_{t+1})=L_t\mathrm{.}$ Consequently $L_{t+1}\le F(q_{t+1})\le L_t$: the objective sequence is nonincreasing.

Expand the finite joint divergence using the update formula for $W_t$: $D(P^{\ast }\mathrm{\parallel }{P}_t)=L_{\beta }^{\ast }+D(q^{\ast }\mathrm{\parallel }{q}_t)-F(q_t)\mathrm{.}$ Indeed $\ln W_t(j\mathrm{\mid }i)=\ln q_t(j)-\beta d_{ij}-\ln Z_i(q_t)$; multiplying $\ln (W^{\ast }\mathrm{/}{W}_t)$ by $p_i{W}_{ij}^{\ast }$ and summing gives the displayed identity. Marginalizing the joint laws over the reproduction coordinate and expanding the finite conditional sums gives $D(P^{\ast }\mathrm{\parallel }{P}_t)=D(q^{\ast }\mathrm{\parallel }{q}_{t+1})+{\sum }_{j:q_j^{\ast }>0}{q}_j^{\ast }D(P^{\ast }(X\in \cdot \mid j)\mathrm{\parallel }{P}_t(X\in \cdot \mid j))\ge D(q^{\ast }\mathrm{\parallel }{q}_{t+1}),$ where [F3] supplies nonnegativity. Thus $F(q_t)-L_{\beta }^{\ast }\le D(q^{\ast }\mathrm{\parallel }{q}_t)-D(q^{\ast }\mathrm{\parallel }{q}_{t+1})$. Since $L_t\le F(q_t)$, the same upper bound holds for $L_t-L_{\beta }^{\ast }$.

Define $s_j(q_t)={\sum }_i{p}_i{e}^{-\beta d_{ij}}\mathrm{/}{Z}_i(q_t)=q_{t+1,j}\mathrm{/}{q}_{t,j}$. For $a_{ij}=e^{-\beta d_{ij}}\mathrm{/}{Z}_i(q_t)$, concavity of $\ln$ and $F(q^{\ast })=L_{\beta }^{\ast }$ give $F(q_t)-L_{\beta }^{\ast }={\sum }_i{p}_i\ln \left({\sum }_j{q}_j^{\ast }{a}_{ij}\right)\le \ln ({\sum }_j{q}_j^{\ast }{s}_j(q_t))\le \ln {\max }_j{s}_j(q_t)=\ln {\gamma }_t\mathrm{.}$ Since $L_t\le F(q_t)$, this proves the stated a-posteriori certificate. Also ${\sum }_j{q}_{t,j}{s}_j(q_t)=1$, so ${\gamma }_t\ge 1$.

Summing step 3.1 for $s=0,\dots ,t$ telescopes to ${\sum }_{s=0}^t(L_s-L_{\beta }^{\ast })\le D(q^{\ast }\mathrm{\parallel }{q}_0)$, since KL is nonnegative. By step 2.2 the gaps are nonincreasing, so $(t+1)(L_t-L_{\beta }^{\ast })\le D(q^{\ast }\mathrm{\parallel }{q}_0)$. If $q_0$ is uniform, $D(q^{\ast }\mathrm{\parallel }{q}_0)=\ln n-H(q^{\ast })\le \ln n$.

The sequence $F(q_t)$ is nonincreasing by step 2.2 and bounded below by $L_{\beta }^{\ast }$. Moreover, $F(q_t)-F(q_{t+1})\ge D(q_{t+1}\mathrm{\parallel }{q}_t)$, so this successive KL divergence tends to zero. Step 4.1 gives $L_t\to L_{\beta }^{\ast }$; the first identity in step 2.2 then gives $F(q_t)\to L_{\beta }^{\ast }$. The simplex is compact, and $F$, each $s_j$, and $\gamma$ are continuous there because every $Z_i(q)\ge {\min }_j{e}^{-\beta d_{ij}}>0$. Every cluster point of $q_t$ is therefore a minimizer of $F$.

At any minimizer $q$ of differentiable $F(q)=-{\sum }_i{p}_i\ln Z_i(q)$, the coordinate derivative is $-s_j(q)$. Moving mass between a positive coordinate and any other coordinate shows $s_j(q)=1$ on the support and $s_j(q)\le 1$ off the support; the active value equals one because ${\sum }_j{q}_j{s}_j(q)=1$. Hence $\gamma (q)=1$ at every minimizer. Compactness and continuity from step 5.1 imply ${\gamma }_t\to 1$: otherwise a subsequence bounded away from one would have a cluster point with the same property. By step 1.2, the enclosure upper endpoints satisfy $u_t\le \ln {\gamma }_t+1\mathrm{/}(t+1)$, so $u_t\to 0$ and every positive tolerance is eventually met. The argument permits zero coordinates in $q^{\ast }$, so boundary minimizers are included.