Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Results and Techniques in Multiuser Information Theory

Amin Aminzadeh Gohari

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2010-115
August 16, 2010

http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-115.pdf

In this dissertation we develop new techniques and apply them to prove new results in multiuser information theory. In the first part of the dissertation, we introduce the ``potential function method," and apply it to prove converses for a series of multiterminal network capacity problems. In the second part of the dissertation, we introduce the ``perturbation method," and apply it to the general broadcast channel problem, a fundamental open problem in information theory. Furthermore, we address a number of computational issues associated with the general broadcast channel. The first part of the dissertation is devoted to the ``potential function method" and its application to multiterminal networks. This method works by finding certain properties of expressions which will imply that they dominate the capacity region, and then proving a given bound by a verification argument. We show that this method can provide a unified framework for proving converses. We begin by considering the category of rate region problems without output feedback. The ``dynamic programming flavor" of the technique and its use of one-step equations are brought up here. To demonstrate the use of technique in problems with feedback, we consider the problem of information-theoretically secure secret key agreement under the well-known \emph{source model} and \emph{channel model}. The concept of ``state" and its evolution during the interactive communication by the parties are brought up here. The upper bounds we prove in this section are new and are strictly better than their corresponding previously best known upper bounds (our new lower bounds are relegated to an appendix in the end of the dissertation as they were not derived using the potential function method). Finally, we demonstrate the use of technique in a problem that involves transmission of dependent sources over strong interference channels. The new feature is that the notion of achievable rate regions is replaced by that of admissible sources. The result proved in this section is also new. The second part of the dissertation begins by discussing the ``perturbation method," and its application to the general broadcast channel problem. The perturbation method is based on an identity that relates the second derivative of the Shannon entropy of a discrete random variable (under a certain perturbation) to the corresponding Fisher information. We apply this tool to make Marton's inner bound for the general broadcast channel computable. Before this, the latter region was not computable (except in certain special cases) as no bounds on the cardinality of its auxiliary random variables existed. The main obstacle in proving cardinality bounds is the fact that the Carath\'{e}odory theorem, the main known tool for proving cardinality bounds, does not yield a finite cardinality result. In order to go beyond the traditional Carath\'{e}odory type arguments, we identify certain properties that the auxiliary random variables corresponding to the extreme points of the inner bound satisfy. These properties are then used to establish cardinality bounds on the auxiliary random variables of the inner bound, thereby proving the computability of the region. We continue the second part of the dissertation with several results on computing a number of regions associated with the general broadcast channels. For instance, we prove various results that help to restrict the search space for computing the sum-rate for Marton's inner bound.

Advisor: Venkat Anantharam


BibTeX citation:

@phdthesis{Aminzadeh Gohari:EECS-2010-115,
    Author = {Aminzadeh Gohari, Amin},
    Title = {Results and Techniques in Multiuser Information Theory},
    School = {EECS Department, University of California, Berkeley},
    Year = {2010},
    Month = {Aug},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-115.html},
    Number = {UCB/EECS-2010-115},
    Abstract = {In this dissertation we develop new techniques and apply them to prove new results in multiuser information theory. In the first part of the dissertation, we introduce the ``potential function method," and apply it to prove converses for a series of multiterminal network capacity problems. In the second part of the dissertation, we introduce the ``perturbation method," and apply it to the general broadcast channel problem, a fundamental open problem in information theory. Furthermore, we address a number of computational issues associated with the general broadcast channel.

The first part of the dissertation is devoted to the ``potential function method" and its application to multiterminal networks. This method works by finding certain properties of expressions which will imply that they dominate the capacity region, and then proving a given bound by a verification argument. We show that this method can provide a unified framework for proving converses. We begin by considering the category of rate region problems without output feedback. The ``dynamic programming flavor" of the technique and its use of one-step equations are brought up here. To demonstrate the use of technique in problems with feedback, we consider the problem of information-theoretically secure secret key agreement under the well-known \emph{source model} and \emph{channel model}. The concept of ``state" and its evolution during the interactive communication by the parties are brought up here. The upper bounds we prove in this section are new and are strictly better than their corresponding previously best known upper bounds (our new lower bounds are relegated to an appendix in the end of the dissertation as they were not derived using the potential function method). Finally, we demonstrate the use of technique in a problem that involves transmission of dependent sources over strong interference channels. The new feature is that the notion of achievable rate regions is replaced by that of admissible sources. The result proved in this section is also new.

The second part of the dissertation begins by discussing the ``perturbation method," and its application to the general broadcast channel problem. The perturbation method is based on an identity that relates the second derivative of the Shannon entropy of a discrete random variable (under a certain perturbation) to the corresponding Fisher information. We apply this tool to make Marton's inner bound for the general broadcast channel computable. Before this, the latter region was not computable (except in certain special cases) as no bounds on the cardinality of its auxiliary random variables existed. The main obstacle in proving cardinality bounds is the fact that the Carath\'{e}odory theorem, the main known tool for proving cardinality bounds, does not yield a finite cardinality result. In order to go beyond the traditional Carath\'{e}odory type arguments, we identify certain properties that the auxiliary random variables corresponding to the extreme points of the inner bound satisfy. These properties are then used to establish cardinality bounds on the auxiliary random variables of the inner bound, thereby proving the computability of the region. We continue the second part of the dissertation with several results on computing a number of regions associated with the general broadcast channels. For instance, we prove various results that help to restrict the search space for computing the sum-rate for Marton's inner bound.}
}

EndNote citation:

%0 Thesis
%A Aminzadeh Gohari, Amin
%T Results and Techniques in Multiuser Information Theory
%I EECS Department, University of California, Berkeley
%D 2010
%8 August 16
%@ UCB/EECS-2010-115
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-115.html
%F Aminzadeh Gohari:EECS-2010-115