Revisit the Arimoto-Blahut algorithm: New Analysis with Approximation

By the seminal paper of Claude Shannon \cite{Shannon48}, the computation of the capacity of a discrete memoryless channel has been considered as one of the most important and fundamental problems in Information Theory.

Nearly 50 years ago, Arimoto and Blahut independently proposed identical algorithms to solve this problem in their seminal papers \cite{Arimoto1972AnAF, Blahut1972ComputationOC}.

The Arimoto-Blahut algorithm was proven to converge to the capacity of the channel as $t \to \infty$ with the convergence rate upper bounded by $O\left(\log(m)/t\right)$, where $m$ is the size of the input distribution, and being inverse exponential when there is a unique solution in the interior of the input probability simplex \cite{Arimoto1972AnAF}.

Recently it was proved, in \cite{Nakagawa2020AnalysisOT}, that the convergence rate is at worst inverse linear $O(1/t)$ in some specific cases.

In this paper, we revisit this fundamental algorithm looking at the rate of convergence to the capacity and the time complexity, given $m,n$, where $n$ is size of the output of the channel, focusing on the approximation of the capacity.

We prove that the rate of convergence to an $\varepsilon$-optimal solution, for any constant $\varepsilon > 0$, is inverse exponential $O\left(\log(m)/c^t\right)$, for a constant $c > 1$ and $O\left(\log \left(\log (m)/\varepsilon\right)\right)$ at most iterations, implying $O\left(m n\log \left(\log (m)/\varepsilon\right)\right)$ total complexity of the algorithm.