Geometric Programming Duals of Channel Capacity and Rate Distortion

Mung Chiang, Stephen Boyd

Research output: Contribution to journalArticlepeer-review

79 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)245-258+410
JournalIEEE Transactions on Information Theory
Volume50
Issue number2
DOIs
StatePublished - Feb 2004

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Channel capacity
  • Convex optimization
  • Duality
  • Free energy
  • Geometric programming
  • Rate distortion

Fingerprint

Dive into the research topics of 'Geometric Programming Duals of Channel Capacity and Rate Distortion'. Together they form a unique fingerprint.

Cite this