Citation
Shadbakht, Sormeh (2011) Entropy region and network information theory. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:06092011140731576
Abstract
This dissertation takes a step toward a general framework for solving network information theory problems by studying the capacity region of networks through the entropy region. We first show that the capacity of a large class of acyclic memoryless multiuser information theory problems can be formulated as convex optimization over the region of entropy vectors of the network random variables. This capacity characterization is universal, and is advantageous over previous formulations in that it is single letter. Besides, it is significant as it reveals the fundamental role of the entropy region in determining the capacity of network information theory problems. With this viewpoint, the rest of the thesis is dedicated to the study of the entropy region, and its consequences for networks. A full characterization of the entropy region has proven to be a very challenging problem, and thus, we mostly consider inner bound constructions. For discrete random variables, our approaches include characterization of entropy vectors with a latticederived probability distribution, the entropy region of binary random variables, and the linear representable region. Through these characterizations, and using matroid representability results, we study linear coding capacity of networks in different scenarios (e.g., binary operations in a network, or networks with two sources). We also consider continuous random variables by studying the entropy region of jointly Gaussian random variables. In particular, we determine the sufficiency of Gaussian random variables for characterizing the entropy region of 3 random variables in general. For more than 3 random variables, we point out the set of minimal necessary and sufficient conditions for a vector to be an entropy vector of jointly Gaussian random variables. Finally, in the absence of a full analytical characterization of the entropy region, it is desirable to be able to perform numerical optimization over this space. In this regard, we propose a certain Monte Carlo method that enables one to numerically optimize entropy functions of discrete random variables, and also the achievable rates in wired networks. This method can be further adjusted for decentralized operation of networks. The promise of this technique is shown through various simulations of several interesting network problems.
Item Type:  Thesis (Dissertation (Ph.D.)) 

Subject Keywords:  Entropy Region, Network Coding, Representable Entropy, Gaussian Entropy, Multiuser Information Theory, Markov Chain Monte Carlo Optimization, QuasiUniform, Group Characterizable 
Degree Grantor:  California Institute of Technology 
Division:  Engineering and Applied Science 
Major Option:  Electrical Engineering 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  16 May 2011 
Author Email:  sormeh (AT) caltech.edu 
Record Number:  CaltechTHESIS:06092011140731576 
Persistent URL:  http://resolver.caltech.edu/CaltechTHESIS:06092011140731576 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  6514 
Collection:  CaltechTHESIS 
Deposited By:  Sormeh Shadbakht 
Deposited On:  14 Jun 2011 22:13 
Last Modified:  18 Jan 2013 00:45 
Thesis Files

PDF
 Updated Version
See Usage Policy. 2636Kb 
Repository Staff Only: item control page