9
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you give an example of such "elegance and intuition" in another context? $\endgroup$
    – kodlu
    Commented Apr 28, 2015 at 21:22
  • $\begingroup$ 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. $\endgroup$
    – luegofuego
    Commented Apr 29, 2015 at 5:44
  • $\begingroup$ 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. $\endgroup$
    – luegofuego
    Commented Apr 29, 2015 at 5:47

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 :)). $\endgroup$
    – Nikos M.
    Commented May 4, 2015 at 23:56
  • $\begingroup$ @ Nikos M., absolutely, and I sympathise. For example, some information theory problems give rise to non-convex capacity regions, e.g., OFDMA. $\endgroup$
    – kodlu
    Commented May 5, 2015 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.