An approximation approach to network information theory

Shannon theory aims for solutions/characterizations to infinite-dimensional design problems and a “single-letter” characterization is one where the solution is reducable to a finite dimensional optimization problem. While such characterizations are powerful and yield significant insight, it is unclear whether many problems in network information theory admit such a solution. In fact, after almost 40 years of effort, few problems in network information theory have been resolved with such a characterization. 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 communicating messages over a noisy network, we develop a deterministic model that focusses on the “interaction” rather than the noise. This simplification allows us to pursue the steps of the program, by simplifying the model, solving it and then translating it to an approximate characterization. This “deterministic approximation” approach has been successfully applied to make progress on many long-standing open problems in network information theory problems. The deterministic model and its application to the approximation of capacity of wireless relay networks have been developed in the paper: Wireless network information flow: a deterministic approach

For network data compression problems, we simplify by replacing the lossy distortion criterion to lossless one. This allows us to gain insight into the network data compression problem and obtain an approximation to the original problem. This was first developed for the multiple description data compression problem in the paper Approximating the Gaussian Multiple Description Rate Region Under Symmetric Distortion.

Using this approach, progress has already been made on several other long-standing open problems.