An Approximation Approach to Network Information Theory

Unique among many engineering fields, information theory aims for and almost demands exactly optimal solutions to infinite-dimensional design problems. Such a high standard was set by Shannon in his original analysis of point-to-point communication problems. After almost 40 years of effort, meeting such a standard has proved to be far more difficult when extending Shannon's theory to networks. We argue that much broader progress can be made when instead one seeks approximate solutions with a guarantee on the gap to optimality. Focusing on the practically important models of linear Gaussian channels and Gaussian sources, our approach consists of three steps: 1) simplify the model; 2) obtain optimal solution for the simplified model; 3) translate the optimal scheme and outer bounds back to the original model. For network channel coding problems, we simplify by replacing the noisy channels by noiseless channels. For network source coding problems, we simplify by replacing the lossy distortion criterion to lossless one. This approach also shows a surprising connection between Gaussian problems and network coding problems on wired networks.

Using this approach, progress has already been made on several long-standing open problems. For a quick overview of the basic ideas, see the following article and presentation:

It is Easier to Approximate, ISIT 2009 plenary talk, IT Newsletter, March 2010. Slides.

Below is an incomplete list of papers if you want to find out more about the details. If you want to add your paper to this list, let me know.

Interference

R. Etkin, D. Tse and H. Wang, "Gaussian Interference Channel Capacity to Within One Bit", , IEEE Transactions on Information Theory, Dec. 2008.

G. Bresler and D. Tse, "The Two-User Gaussian Interference Channel: A Deterministic View", vol 19, European Transactions in Telecommunications, pp. 333-354, April 2008.

G. Bresler, A. Parekh and D. Tse, The Approximate Capacity of the Many-to-One and One-to-Many Gaussian Interference Channels , submitted to Transactions on IT, Sept 2008.

C. Suh, D. Tse, Symmetric Feedback Capacity of the Gaussian Interference Channel to Within One Bit, ISIT 2009.

P. Minero, M. Francheschetti and D. Tse, Random Access: An Information-Theoretic Perspective, submitted to IEEE Transactions on IT, Dec, 2009.

I-Hsiang Wang and D. Tse, Interference Mitigation Through Limited Receiver Cooperation, submitted to IEEE Transactions on IT, Nov, 2009.

Relay

S. Avestimehr, S. Diggavi and D. Tse, Wireless network information flow: a deterministic approach, submitted to Transactions on IT, June 2009.

Broadcast

D. Tse and R. Yates, Fading Broadcast Channels with State Information at the Receivers, submitted to Transactions on IT, April 2009.

Multiple Description

C. Tian, S. Mohajer, S. Diggavi, Approximating the Gaussian Multiple Description Rate Region Under Symmetric Distortion Constraints, submitted to Transactions on IT, Oct. 2008.

Lossy Source Coding

M. Maddah-Ali, D. Tse Approximating the Rate-Distortion Region of the Distributed Source Coding for Three Jointly Gaussian Tree-Structured Sources, ISIT 2009.