Despite significant advances in information theory and its application to point-to-point communications, a general theory governing optimal information flow over networks does not yet exist. Except for a few simple network models, the capacity region of a general memoryless network remains unknown, due to the complex tradeoff between competition and cooperation among many nodes in the network. Modern applications such as sensor networks, peer-to-peer systems, and distributed storages further bring up a new set of challenging problems spanning control, estimation, compression, computation, communication, as well as networking.
This research program provides a common set of conceptual, mathematical, and algorithmic tools for the emerging convergence of computation, control, and communication over networks, with the ultimate goal of developing a unified framework for characterizing fundamental performance limits of such systems. Towards this goal, we focus on three concrete problems representing the intersection of computation, control, and communication -- 1) the capacity of the relay channel (how to summarize the relay's noisy observation of the codeword: a list intersection technique via coding for distributed computing), 2) networked control (how to summarize the observation to stabilize a linear dynamical system: a variant of rate distortion coding for control), 3) collision avoidance for multiple access (how to build cooperation from a common source of randomness: a distributed generation of correlated random variables). Novel coding schemes will be proposed, while classical coding techniques will be reinterpreted and extended to broader applications. An algebraic framework for capacity regions is also developed to check the optimality of such coding schemes. The research program is complemented by educational activities that include the curriculum development for a graduate course on network information theory and the writing of an accompanied textbook.
In this project, we investigated fundamental limits on information flow over networks and optimal coding schemes that achieve these limits. There are three main areas we have made significant contributions. Wireless relaying. We developed the "noisy network coding" scheme for a general network with noise, interference, and broadcast. By combining and extending "network coding" for wired networks and compress--forward relaying, this scheme achieves the best-known performance for multicast over general wireless networks. In addition, we developed a set of mathematical techniques to analyze the performance of the coding scheme that can be applied to other coding schemes and communication scenarios. Broadly speaking, this result provides a new perspective on wireless relaying and the coding scheme is expected to be applied to future wireless networks. Simultaneous communication of data and channel state information. We asked how much information we can communicate reliably over a given channel and how much we can learn about the channel itself at the same time. Under several measures for the fidelity of channel estimation and availability settings of the channel state information at the encoder, we have established the optimal tradeoff between the information transmission rate and the channel state estimation error. Broadly speaking, this result provides a design guidance in practical communication systems in which channel state information is an integral part. Sparse signal processing. We studied how one can represent a signal by a linear combination of as few reference signals from a dictionary as possible. We characterized the fundamental tradeoff between the dictionary size, the sparsity of the representation, and the fidelity of the representation. In a dual development, we established a similar tradeoff when one wishes to recover the location of nonzero elements in a sparse signal. Broadly speaking, these results provide a new set of analysis tools from network information theory that can be applied to signal processing problems. We also investigated the capacity of multiple-write memory, which is a mathematical model for flash memory, and proposed new interactive relaying schemes that perform better than traditional noninteractive relaying schemes. In addition to these research activities that advanced our theoretical understanding of communication, estimation, and signal processing, the project contributed a new textbook "Network Information Theory" published in November 2011, which provided the first comprehensive treatment on the subject. Built on a unified pedagogical framework, this textbook has been used widely in many academic institutions around the world and made many results and tools from network information theory more accessible to a broader audience.
