# Information theory and convex optimization

I'm taking a graduate level course in information theory and I'm constantly struck by how much convex optimization there is in this subject. However, the proofs seem to shy away from using the full machinery of relaxation theory, duality, etc. This is understandable since you don't want to require a full semester of convex optimization in order to teach this stuff. But as someone fairly well-versed in optimization, I feel like I'm missing out on a lot of elegance and intuition when these links aren't explored more. I often notice proofs that would be way shorter if you had utilized convex analysis as well.

Are there books that cover information theory more from this perspective? We're mostly using lecture notes from Stefan Moser, Y. Polyanskiy and Y. Wu, as well as Network Information Theory by El Gamal.

• Can you give an example of such "elegance and intuition" in another context? Apr 28, 2015 at 21:22
• Well, as one of many examples, we were talking about saddle point properties of the channel capacity. I believe it's called the KL divergence minmax formulation or something. It's covered fairly well in the Polyanskiy notes I mentioned above. What struck me is that it seemed to be exactly a re-statement of Lagrangian relaxation/duality in a different context. Apr 29, 2015 at 5:44
• A slightly more mundane example might be when we were asked to prove the convexity of the rate distortion function, which is a one line proof if you recall some properties of infimums over convex sets etc. Apr 29, 2015 at 5:47

The books below may be more to your liking, but in general, the texts/lecture notes are written for the use of (mainly) postgraduate students in engineering and cannot presume deep knowledge of convex analysis.

1. Csizsar, I., and Korner, J., Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd Ed, Cambridge.
2. Berger, T., Rate Distortion Theory, quite old probably late 70's or early 80s, can't remember the publisher maybe Wiley.
3. Yeung, R.W., A First Course in Information Theory, Springer.

The research articles on Shannon theory and related fields in, say, IEEE Transactions on Information Theory, may fit the bill better, though not always.

An older text which may also be of interest is

Wolfowitz, J., Coding Theorems of Information Theory, Springer, 1960's.

• just a comment, it depends on what one would consider as "deep", for example i consider information theory as deeper than convex analysis (for example because it has more applications to diverse fields) and i prefer to reduce convex analysis to information theory instead of vice-versa. It can be done if one wants to (lets say how category-theorists would like to reduce everything to categoriers instead of algebra :)). May 4, 2015 at 23:56
• @ Nikos M., absolutely, and I sympathise. For example, some information theory problems give rise to non-convex capacity regions, e.g., OFDMA. May 5, 2015 at 0:05