Blahut–Arimoto algorithm

The Blahut–Arimoto algorithm, is often used to refer to a class of algorithms for computing numerically either the information theoretic capacity of a channel, or the rate-distortion function of a source. They are iterative algorithms that eventually converge to the optimal solution of the convex optimization problem that is associated with these information theoretic concepts.

History and application

For the case of channel capacity, the algorithm was independently invented by Suguru Arimoto[1] and Richard Blahut.[2] In the case of lossy compression, the corresponding algorithm was invented by Richard Blahut. The algorithm is most applicable to the case of arbitrary finite alphabet sources. Much work has been done to extend it to more general problem instances.[3][4] Recently, a version of the algorithm that accounts for continuous and multivariate outputs was proposed with applications in cellular signaling [5]. There exists also a version of Blahut–Arimoto algorithm for directed information[6].

Algorithm

Suppose we have a source ${\displaystyle X}$ with probability ${\displaystyle p(x)}$ of any given symbol. We wish to find an encoding ${\displaystyle p({\hat {x}}|x)}$ that generates a compressed signal ${\displaystyle {\hat {X}}}$ from the original signal while minimizing the expected distortion ${\displaystyle \langle d(x,{\hat {x}})\rangle }$, where the expectation is taken over the joint probability of ${\displaystyle X}$ and ${\displaystyle {\hat {X}}}$. We can find an encoding that minimizes the rate-distortion functional locally by repeating the following iteration until convergence:

${\displaystyle p_{t+1}({\hat {x}})=\sum _{x}p(x)p_{t}({\hat {x}}|x)}$

${\displaystyle p_{t+1}({\hat {x}}|x)={\frac {p_{t}({\hat {x}})\exp(-\beta d(x,{\hat {x}}))}{\sum _{\hat {x}}p_{t}({\hat {x}})\exp(-\beta d(x,{\hat {x}}))}}}$

where ${\displaystyle \beta }$ is a parameter related to the slope in the rate-distortion curve that we are targeting and thus is related to how much we favor compression versus distortion (higher ${\displaystyle \beta }$ means less compression).

References

1. Arimoto, Suguru (1972), "An algorithm for computing the capacity of arbitrary discrete memoryless channels", IEEE Transactions on Information Theory, 18 (1): 14–20, doi:10.1109/TIT.1972.1054753, S2CID 8408706.
2. Blahut, Richard (1972), "Computation of channel capacity and rate-distortion functions", IEEE Transactions on Information Theory, 18 (4): 460–473, CiteSeerX 10.1.1.133.7174, doi:10.1109/TIT.1972.1054855.
3. Pascal O. Vontobel (2002). A Generalized Blahut–Arimoto Algorithm. CiteSeerX 10.1.1.1.2567.
4. Iddo Naiss; Haim Permuter (2010). "Extension of the Blahut-Arimoto algorithm for maximizing directed information". arXiv:1012.5071v2 [cs.IT].
5. Tomasz Jetka; Karol Nienaltowski; Tomasz Winarski; Slawomir Blonski; Michal Komorowski (2019), "Information-theoretic analysis of multivariate single-cell signaling responses", PLOS Computational Biology, 15 (7): e1007132, arXiv:1808.05581, Bibcode:2019PLSCB..15E7132J, doi:10.1371/journal.pcbi.1007132, PMC 6655862, PMID 31299056
6. Naiss, Iddo; Permuter, Haim H. (January 2013). "Extension of the Blahut–Arimoto Algorithm for Maximizing Directed Information". IEEE Transactions on Information Theory. 59 (1): 204–222. doi:10.1109/TIT.2012.2214202.