The capacity of a noisy channel $\mathcal{E}_{X\rightarrow Y}$, where the channel is given as a conditional probability distribution $p(y|x)$, is

$$C = \max_{p_X}I(X:Y),$$

where $I(X:Y)$ is the mutual information and $p_X$ is the input probability distribution. This optimization problem is concave. The Blahut-Arimoto algorithm is commonly used to find the solution of this optimization problem.

My question is, why was this algorithm developed? Since the problem is a convex optimization problem, why can we not use standard methods such as gradient descent to solve it? Is it that the Blahut-Arimoto algorithm is more efficient or something else? I have read the original paper of Arimoto but it doesn't compare their method to standard convex optimization problem techniques.

  • $\begingroup$ Mutual information is neither convex nor concave in the joint distribution. See this question on Mathematics. $\endgroup$ Apr 22 '20 at 13:26
  • $\begingroup$ @YuvalFilmus we only maximize over $p(x)$ (the input distribution), not $p(x,y)$ (the joint distribution). As mentioned in that question, "It is well known that, for fixed $p(y|x)$, mutual information is a concave function of $p(x)$ (e.g. see Theorem 2.7.4 in Cover & Thomas)". The channel is given to us and we only optimize over all possible input distributions to the channel. Does that make sense or did I misunderstand you? $\endgroup$ Apr 22 '20 at 13:56
  • $\begingroup$ Cover & Thomas (Elements of information theory) mention several algorithms for computing channel capacity: constrained maximization using the KKT conditions; Frank-Wolfe; and Arimoto–Blahut. Perhaps Blahut–Arimoto is more efficient. They only bother describing the algorithm in detail in the context of rate-distortion theory, so perhaps it's more important there, and for channel capacity other algorithms could indeed be used. $\endgroup$ Apr 22 '20 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.