TY - JOUR
T1 - Geometric Programming Duals of Channel Capacity and Rate Distortion
AU - Chiang, Mung
AU - Boyd, Stephen
N1 - Funding Information:
Manuscript received January 6, 2003; revised October 6, 2003. This work was supported by the Hertz Foundation Fellowship and the Stanford Graduate Fellowship. The material in this paper was presented in part at the 40th Allerton Conference on Communication, Control and Computing, Monticello, IL, October 2002, and the IEEE International Symposium on Information Theory, Yokohama, Japan, June/July 2003. M. Chiang is with the Electrical Engineering Department, Princeton University, Princeton, NJ 08544 USA (e-mail: [email protected]). S. Boyd is with the Electrical Engineering Department, Stanford University, Stanford, CA 94305 USA (e-mail: [email protected]). Communicated by R. W. Yeung, Associate Editor for Shannon Theory. Digital Object Identifier 10.1109/TIT.2003.822581
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2004/2
Y1 - 2004/2
N2 - 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 dual characterization is shown to be equivalent to the minmax Kullback-Leibler (KL) characterization in [10], [14]. 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.
AB - 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 dual characterization is shown to be equivalent to the minmax Kullback-Leibler (KL) characterization in [10], [14]. 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.
KW - Channel capacity
KW - Convex optimization
KW - Duality
KW - Free energy
KW - Geometric programming
KW - Rate distortion
UR - http://www.scopus.com/inward/record.url?scp=10744227892&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=10744227892&partnerID=8YFLogxK
U2 - 10.1109/TIT.2003.822581
DO - 10.1109/TIT.2003.822581
M3 - Article
AN - SCOPUS:10744227892
SN - 0018-9448
VL - 50
SP - 245-258+410
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 2
ER -