# Capacity of channels: Why do we need Blahut-Arimoto algorithms?

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.

• Mutual information is neither convex nor concave in the joint distribution. See this question on Mathematics. Apr 22 '20 at 13:26
• @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? Apr 22 '20 at 13:56
• 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. Apr 22 '20 at 14:07