Geometric Programming Duals of Channel Capacity and Rate Distortion

IEEE Transactions in Information Theory, 50(2):245-258, February 2004.
Shorter versions appeared in Proceedings of the Allerton Conference 2002 and in IEEE International Symposium on Information Theory 2003, p291-292.

• gp_chan_cap.pdf

We show that the Lagrange dual problems of the channel capacity problem with input cost and the rate distortion problem are simple geometric programs. Upper bounds on channel capacity and lower bounds on rate distortion can be efficiently generated from their duals. For channel capacity, the geometric programming characterization is shown to be equivalent to the minmaxKL characterization. For rate distortion, the geometric programming dual is extended to rate distortion with two-sided state information. A ‘duality by mapping’ is then given between the Lagrange dual problems of channel capacity with input cost and rate distortion, which resolves several apparent asymmetries between their primal problems in the familiar form of mutual information optimization problems. Both the primal and dual problems can be interpreted in a common framework of free energy optimization from statistical physics.