Canonical Representation of Achievable Region in Mutiterminal Source Coding

Since Shannon's pioneering discovery of the mathematical principle behind one-terminal source coding, Shannon-type single-letter descriptions have been sought for more general problems. However, till recently, only a handful of specific problems, including the respective ones due to Slepian and Wolf, Wyner, Ahlswede and Korner, Wyner and Ziv, and Berger and Yeung, were known to allow the desired single-letter characterization. In other words, single-letter descriptions have enjoyed limited success in capturing a general principle behind the class of multiterminal source coding. In contrast, we obtain a canonical representation for this class, which is based on Slepian-Wolf theorem, and not necessarily of single-letter type. Further, we show that our representation reduces to single-letter for a broad subclass of multiterminal problems, where all but at most one sources are perfectly reconstructed with or without the help of side information available at the decoder!
Not surprisingly, the above subclass includes all aforementioned problems as special cases. Moreover, our theory completely solves the single-helper problem of Csiszar and Korner, which remained open in the general case. In light of our result, generic multiterminal problems can now be divided into two braod categories: (1) easy (completely solved) problems, where at most one source is not perfectly reconstructed, and which admit single-letter descriptions, and (2) difficult (in general, open) problems, where more than one sources are not perfectly reconstructed, and which in general are not known to admit single-letter descriptions. In this talk, we shall see that a fundamental structural difference exists between the above two categories. Specifically, the factor graph corresponding to the information-theoretic description involves no cycles in the former category, and irreducible cycles in the latter. Further, for the 'difficult' problems, although our representation does not take a simple form, we still have a hierarchical description. Histortically, some researchers, such as Csiszar and Korner, do refer to similar (yet less effective) hierachical characterizations; however, their usefulness has so far not been realized. We break new ground by pointing out useful properties of our hierarchical representation, which potentially leads to efficient computational methods based on divide-and-conquer policy. Specifically, we shall see that our factor-graphs in question can be built in a modular fashion, where the lower-order graphs suggest good starting point for higher-order ones.

Soumya Jana was born in Calcutta, India, in 1973. He graduated from the Indian Institute of Technology, Kharagpur, in 1995 with a B. Tech. in Electronics and Electrical Communication Engineering. He went on to obtain an M. E. in Electrical Communication Engineering from the Indian Institute of Science, Bangalore, in 1997, and a Ph. D. in Electrical Engineering from University of Illinois, Urbana-Champaign, in 2005. Before joining the University of Illinois, he worked as a software engineer at Silicon Automation Systems in Bangalore. Since 2006, he has been continuing his research at the University of Illinois as a postdoctoral research associate. His research interests include multiterminal source coding, decision theory, transform coding and quantization, and broadcast channel coding.