2658 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
Duality, Achievable Rates, and Sum-Rate Capacity of
Gaussian MIMO Broadcast Channels
Sriram Vishwanath, Student Member, IEEE, Nihar Jindal, Student Member, IEEE, and
Andrea Goldsmith, Senior Member, IEEE
Abstract—We consider a multiuser multiple-input multiple-
output (MIMO) Gaussian broadcast channel (BC), where the
transmitter and receivers have multiple antennas. Since the
MIMO BC is in general a nondegraded BC, its capacity region
remains an unsolved problem. In this paper, we establish a duality
between what is termed the “dirty paper” achievable region (the
Caire–Shamai achievable region) for the MIMO BC and the
capacity region of the MIMO multiple-access channel (MAC),
which is easy to compute. Using this duality, we greatly reduce
the computational complexity required for obtaining the dirty
paper achievable region for the MIMO BC. We also show that the
dirty paper achievable region achieves the sum-rate capacity of
the MIMO BC by establishing that the maximum sum rate of this
region equals an upper bound on the sum rate of the MIMO BC.
Index Terms—Broadcast channel (BC), channel capacity, dirty
paper coding, duality, multiple-input multiple-output (MIMO)
systems.
I. INTRODUCTION
MULTIPLE-input multiple-output (MIMO) systemshave received a great deal of attention as a method to
achieve very high data rates over wireless links. The capacity
of single-user MIMO Gaussian channels was first studied by
Foschini [1] and Telatar [2]. This work has also been extended
to the MIMO multiple-access channel (MAC) [2]–[4]. The
capacity of MIMO broadcast channels (BC), however, is an
open problem due to the lack of a general theory on nonde-
graded BCs. In pioneering work by Caire and Shamai [5], a
set of achievable rates (the achievable region) for the MIMO
BC was obtained by applying the “dirty paper” result [6] at
the transmitter (or alternatively, coding for noncausally known
interference). It was also shown in [5], [7], that the sum rate
MIMO BC capacity equals the maximum sum rate of this
achievable region for the two-user BC with an arbitrary number
of transmit antennas and one receive antenna at each
receiver . However, computing this region is
extremely complex and the approach used in [5], to prove the
optimality of dirty paper coding for sum rate does not appear to
work for the more general class of channels (i.e., an arbitrary
number of users and receive antennas) which we consider.
Manuscript received August 29, 2002; revised June 27, 2003. The material in
this paper was presented at the IEEE International Conference on Communica-
tions, New York, NY, April 2002.
The authors are with the Department of Electrical Engineering, Stanford Uni-
versity, Stanford, CA 94305 (e-mail: [email protected]; njindal@
systems.stanford.edu; [email protected]).
Communicated by G. Caire, Associate Editor for Communications.
Digital Object Identifier 10.1109/TIT.2003.817421
In this paper, we consider a -user MIMO Gaussian BC in
which receiver has receive antennas and the transmitter
has transmit antennas. The achievable region for a general
MIMO BC requires an extension of the Caire–Shamai region to
multiple users and multiple receive antennas, which was done
by Yu and Cioffi in [8]. We refer to this extension as the dirty
paper region. We establish a duality between the dirty paper
region of the MIMO BC and the capacity region of the MIMO
MAC. In other words, we show that the dirty paper region is
exactly equal to the capacity region of the dual MIMO MAC,
with the transmitters having the same sum power constraint
as the MIMO BC. We establish this duality by showing that all
rates achievable in the dual MIMO MAC with power constraints
whose sum equals the BC power constraint are also achievable
in the MIMO BC, and vice versa. This duality is the multiple-
antenna extension of the previously established duality between
the scalar Gaussian BC and MAC [9]. Though we consider only
the constant channel case, this duality can easily be shown to
hold for fading multiple-antenna Gaussian BCs and MACs, as
it does in the scalar channel case. This duality has two important
applications: it permits us to compute with ease the dirty paper
region of the MIMO BC, which is very difficult to compute
directly, and it allows us to show that the dirty paper achievable
region achieves the sum rate capacity of the MIMO BC.
Finding the full capacity region of the MIMO BC is very dif-
ficult due to its nondegraded nature, but we are able to show
that the dirty paper region achieves the sum rate capacity of
the MIMO BC through the use of the Sato upper bound on
the sum-rate capacity of BCs [10]. The Sato upper bound was
first applied to the MIMO BC by Caire and Shamai [5] to find
the sum rate capacity of the channel.
Using Sato’s technique, we bound the sum rate capacity of the
MIMO BC by considering the capacity when the receivers
perform joint signal detection (i.e., we consider a single-user
antenna channel) with the worst case colored
noise, when the noise at every antenna is correlated with the
noise at every other antenna except for those at the same re-
ceiver, and we analytically show, employing a proof which gen-
erally constructs the worst case noise covariance matrix, that
this upper bound coincides exactly with the maximum achiev-
able sum rate in the dirty paper region.
There has been parallel work on the optimality of the dirty
paper region for sum capacity of the BC. In [11], the authors
handle those channels for which the worst case correlation of
the noise in the Sato upper bound is nonsingular, and in [12],
the authors handle channels with multiple transmit antennas but
only one antenna at each receiver. In this paper, we deal with
0018-9448/03$17.00 © 2003 IEEE
VISHWANATH et al.: DUALITY, ACHIEVABLE RATES, AND SUM-RATE CAPACITY OF GAUSSIAN MIMO BROADCAST CHANNELS 2659
the most general case, with no restrictions on the number of
antennas or on the worst case noise.
Although the optimality of the dirty paper region has only
been shown for sum rate (and trivially for the corner points of
the region), the fact that the dirty paper region is equal to the
dual MIMO MAC capacity region together with the fact that the
scalar Gaussian BC capacity region is equal to the dual MAC ca-
pacity region leads us to believe that the dirty paper region may
actually be the capacity region of the MIMO BC. Significant
progress toward proving this conjecture has recently been made
[13], [14], but this hypothesis remains unproven.
The remainder of this paper is organized as follows. In Sec-
tion II, we describe the MIMO BC and the dual MIMO MAC.
In Section III, we summarize some background information,
including the achievable “dirty paper” BC region, the MIMO
MAC capacity region, and the duality of the scalar MAC and
BC. We describe the MIMO MAC–BC duality result in Section
IV. In Section V, we show that the dirty paper region achieves
sum rate capacity of the MIMO BC and we provide a few illus-
trative examples in Section VI. We conclude with Section VII.
II. SYSTEM MODEL
We use boldface to denote matrices and vectors. denotes
the determinant and the inverse of a square matrix . For
any general matrix , denotes the conjugate transpose
and denotes the trace. denotes the identity matrix and
denotes a diagonal matrix with the entry equal
to .
We consider a MIMO BC with a -antenna transmitter and
receivers with receive antennas, respectively. The
transmitter sends independent information to each receiver. The
BC is the system on the left in Fig. 1.
Let be the transmitted vector signal and let
be the channel matrix of receiver where rep-
resents the channel gain from transmit antenna to antenna of
receiver . The white Gaussian noise at receiver is represented
by where . Let be the
received signal at receiver . The received signal is mathemati-
cally represented as
.
.
.
.
.
.
where ..
.
(1)
The matrix represents the channel gains of all receivers. The
covariance matrix of the input signal is . The
transmitter is subject to an average power constraint , which
implies . We assume the channel matrix
is constant and is known perfectly at the transmitter and at all
receivers.
Now consider the dual MAC shown in the right half of Fig. 1.
The dual channel is arrived at by converting the receivers in the
BC into transmitters in the MAC and converting the -antenna
transmitter into a -antenna receiver. Notice that the channel
gains of the dual MAC are the same as that of the BC, i.e.,
corresponds to the gain from transmit antenna to an-
tenna of receiver in the BC and to the gain from antenna of
transmitter to receive antenna in the MAC.
Fig. 1. System models of the MIMO BC (left) and the MIMO MAC (right)
channels.
Let be the transmitted signal of transmitter . Let
be the received signal and the noise vector
where . The received signal is mathematically
represented as
.
.
.
where
In the dual MAC, each transmitter is subject to an individual
power constraint of , with (i.e., the
sum of the MAC power constraints equals the BC power con-
straint). We also assume perfect knowledge of the channel at the
transmitters and the receiver in the dual MAC.
Finally, we define the cooperative system to be the same as the
BC, but with all receivers coordinating to perform joint detec-
tion. If the receivers are allowed to cooperate, the BC reduces to
a single-user multiple-antenna system described
by
(2)
where
.
.
.
and ..
.
We call the capacity of this system the cooperative capacity.
We use
and
to denote the capacity regions of the MIMO BC, MIMO MAC,
and cooperative system, respectively.
III. BACKGROUND
To obtain our results, we use the achievable region of the
MIMO BC channel obtained in [5], [8] and results on the MIMO
MAC capacity region [2]–[4], extensively in this paper. Hence,
we first summarize these results and then state results on the du-
ality of the scalar Gaussian BC and MAC [9].
2660 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
A. Achievable BC Region—The Dirty Paper Region
An achievable region for the MIMO BC was first obtained in
[5]. In [8], the region was extended to the more general mul-
tiple-user, multiple-antenna case using the following extension
of dirty paper coding [6] to the vector case.
Lemma 1 (Yu, Cioffi): Consider a channel with
, where is the received vector, the
transmitted vector, the vector Gaussian interference, and
the vector white Gaussian noise. If and are independent
and noncausal knowledge of is available at the transmitter
but not at the receiver, then the capacity of the channel is the
same as if were not present.
In the MIMO BC, this result can be applied at the transmitter
when choosing codewords for different receivers. The trans-
mitter first picks a codeword for receiver 1. The transmitter then
chooses a codeword for receiver 2 with full (noncausal) knowl-
edge of the codeword intended for receiver 1. Therefore, re-
ceiver 2 does not see the codeword intended for receiver 1 as
interference. Similarly, the codeword for receiver 3 is chosen
such that receiver 3 does not see the signals intended for re-
ceivers 1 and 2 as interference. This process continues for all
receivers. Receiver 1 subsequently sees the signals intended
for all other users as interference, receiver 2 sees the signals
intended for users 3 through as interference, etc. Since the
ordering of the users clearly matters in such a procedure, the
following is an achievable rate vector:
(3)
The dirty paper region is defined as the convex
hull of the union of all such rates vectors over all positive
semidefinite covariance matrices such that
and over all permutations
(4)
where is given by (3). The transmitted signal is
and the input covariance matrices are of the form
. The dirty paper coding procedure yields statisti-
cally independent signals , from which it follows that
.
One important feature to notice about the dirty paper rate
equations in (3) is that the rate equations are neither a concave
nor a convex function of the covariance matrices. This makes
finding the dirty paper region very difficult, because generally
the entire space of covariance matrices which meet the power
constraint must be searched over. In this paper, we consider the
dirty paper region subject to a transmit power constraint. Recent
work [15] has characterized the dirty paper region subject to in-
dividual rate constraints (i.e., minimizing the transmit power re-
quired to achieve a certain set of rates).
B. MIMO MAC Capacity Region
The capacity region of a general MIMO MAC was obtained
in [2]–[4]. We now describe this capacity region for the dual
MIMO MAC as defined in Section II. For any set of powers
, the capacity of the MIMO MAC is
(5)
For , we denote by the following set:
(6)
By the argument provided in [4, Theorem 1], this region is
convex. It can easily be shown that this region is the capacity
region of a MAC when the transmitters have a sum power
constraint instead of individual power constraints but are not
allowed to cooperate. Additionally, the MIMO MAC rates can
be shown to be a concave function of the covariance matrices.
This implies that the boundary points (and the corresponding
covariance matrices) of the sum power MIMO MAC capacity
region can be found by a standard convex program (see [4]
for a discussion of this with regards to the individual power
constraint MIMO MAC, which is nearly identical in structure).
This fact turns out to be quite important because later we show
that the MIMO MAC sum power constraint region is equal to
the dirty paper achievable region of the dual MIMO BC.
C. Duality of the Scalar Gaussian MAC and BC
Finally, we state the duality result for scalar Gaussian MAC
and BC channels [9].
Theorem 1 (Jindal, Vishwanath, Goldsmith): The capacity
region of a scalar Gaussian BC with power and channels
is equal to the union of capacity regions of the dual
MAC with powers such that
The proof of this is obtained by showing that any set of rates
achievable in the BC is also achievable in the MAC, and vice
VISHWANATH et al.: DUALITY, ACHIEVABLE RATES, AND SUM-RATE CAPACITY OF GAUSSIAN MIMO BROADCAST CHANNELS 2661
versa. One key point is that to achieve the same rate vector in the
BC and MAC, the decoding order must in general be reversed,
i.e., if user 1 is decoded last in the BC then user 1 is decoded
first in the MAC. In the next section, we will derive a similar
result that equates the dirty paper BC achievable region with
the union of MAC capacity regions for the MIMO channel we
are considering.
IV. DUALITY OF THE MAC AND DIRTY PAPER BC REGION
In this section, we show that the capacity region of the
MIMO MAC with a sum power constraint of for the
transmitters is the same as the dirty paper region of the dual
MIMO BC with power constraint . In other words, any
rate vector that is achievable in the dual MAC with power
constraints is in the dirty paper region of the BC
with power constraint . Conversely, any rate vector
that is in the dirty paper region of the BC is also in the dual
MIMO MAC region with the same total power constraint.
Theorem 2: The dirty paper region of a MIMO BC channel
with power constraint is equal to the capacity region of the
dual MIMO MAC with sum power constraint
Proof: We first prove by
showing that every rate vector achieved by successive decoding
in the MAC is also in the dirty paper region of the dual MIMO
BC. More specifically, we show by the MAC-to-BC transfor-
mations below that for every set of MAC covariance matrices
and any decoding order in the MAC, there exist
BC covariance matrices using the same sum power
as the MAC (i.e., ) such that
the MAC rates are achievable in the BC using the dirty paper
coding method described in Section III-A. Each set of MAC co-
variance matrices corresponds to a -dimensional polyhedron,
as described in (5), with the corner points of the polyhe-
dron corresponding to performing successive decoding at the
receiver in one of the possible decoding orders. By the con-
vexity of the dirty paper region (due to the convex hull opera-
tion), it is sufficient to show that the corner points of all poly-
hedrons (i.e., the successive decoding points) corresponding to
all MAC covariance matrices are in the dirty paper region of the
dual MIMO BC. Thus, with the MAC-to-BC transformations
described below, this implies .
We complete the proof by showing
We prove this by showing (via the BC-to-MAC transformations
below) that for every set of BC covariance matrices and any en-
coding order there exist MAC covariance matrices that achieve
the same set of rates using the same sum power. The convexity
of the MIMO MAC sum power constraint region thus implies
that
This completes the proof, provided we have the transformations
given below that map the MAC covariances to the BC covari-
ances and vice versa.
Next, we explain some terminology used in the transforma-
tions, followed by the actual transformations. It is important
to point out that the transformations require a reverses de-
coding/encoding order of the users in the dual MAC/BC
channel. In other words, if user 1 is decoded first in the MAC
(i.e., user 1 suffers interference of all other users’ signals), then
we must encode user 1’s signal last (i.e., no interference from
other users) in the BC to achieve the same rates using these
transformations. Also, notice that the proof of duality only
requires existence of BC covariance matrices which satisfy
the rates achieved by a set of MAC covariance matrices, and
vice versa. However, the transformations that follow actually
provide equations for the transformed BC covariances as a
function of the MAC covariances, and vice versa. This can
be quite useful because it is generally much easier to find the
optimal BC covariance matrices by finding the optimal MIMO
MAC covariance matrices and then transforming the matrices
to BC covariance matrices (due to the convex structure of the
MIMO MAC rate equations) than it is to directly search for the
optimum BC covariance matrices.
A. Terminology
First, we explain the terms effective channel and flipped
channel. A single-user MIMO system with channel matrix
, additive Gaussian noise with covariance , and additive
independent Gaussian interference with covariance is said to
have an effective channel of . The set of rates
achievable by and a different system with channel matrix
equal to the effective channel and with additive white noise
of unit variance and no interference are the same. Also, the
capacity of a system with effective channel matrix and
the capacity of system with effective channel matrix ,
termed the flipped channel, are the same [2]. In other words,
for every transmit covariance in , there exists a in
with such that the rate achieved by in is
equal to the rate achieved by in . In Appendix, Section A,
we show that meets this criterion where the
singular value decomposition (SVD) of is where
is square and diagonal.1 Next, we describe the covariance
transformations.
B. MAC-to-BC Transformation
In this subsection, we derive a transformation that takes as
inputs a set of MAC covariance matrices and a decoding order
and outputs a set of BC covariances with the same sum power
as the MAC covariances that achieve rates equal to the rates
achieved in the MAC using the MAC covariance matrices and
successive decoding with the specified decoding order.
Since the numbering of the users is arbitrary , we assume that
user 1 is decoded first, user 2 second, and so on, at the MAC
receiver.
Let
1Note that the standard SVD command in MATLAB does not always return a
square and diagonal matrix of singular values, so modification may be necessary
to generate the flipped matrix correctly.
2662 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
and
The rate achieved by user in the MAC for some arbitrary set
of positive semidefinite covariance matrices is
given by
Notice that represents the interference experienced by user
in the MAC. To simplify, we take the square root of and
use the property . We also introduce
into the expression to get
Treating as the effective channel of the system,
we flip the channel and find such that
Now consider the rate of user in the BC assuming that the
opposite encoding order is used (i.e., user 1 is encoded last, user
2 second to last, etc.)
Here represents the interference experienced by user in the
BC. If we chose the BC covariances as
(8)
.
.
.
(9)
.
.
.
(10)
clearly we see . Additionally, it is easy to show that
the resulting covariance matrices are all symmetric and positive
semidefinite. In Appendix, Section B, we show that the trans-
formations given by (8)–(10) satisfy the sum trace constraint,
or that . Note that depends
only on , and hence, the can be computed se-
quentially in increasing order. By doing this for all users, we
find covariance matrices for the BC that achieve the same rate
as in the MAC. If we substitute in the expression generating the
flipped channel, the expression for the BC covariance matrix of
the th user (9) can be expanded as
(11)
where the effective channel is decomposed
using the SVD as , where is a
square and diagonal matrix.
C. BC-to-MAC Transformation
In this subsection, we derive a transformation which, given
a set of BC covariance matrices and an encoding order, out-
puts a set of MAC covariances with the same sum power as the
BC covariances that achieve MAC rates (using successive de-
coding) equal to the rates achieved in the BC using the BC co-
variance matrices. These transformations are almost identical to
the MAC-to-BC transformations. For the dirty paper encoding
at the BC, we assume that user is encoded first, user
second, and so on, in decreasing order. Along the same lines as
the MAC–BC transformation, we treat as the
effective channel and as the covariance matrix. By
flipping the effective channel, we obtain and ob-
tain the transformation
(12)
.
.
.
(13)
.
.
.
(14)
As before, if we use the opposite decoding order in the MAC
(i.e., user 1 decoded first, etc.), this transformation ensures that
the rates of all users in the BC and MAC are equivalent along
with the total power used in the BC and MAC. Also note that
we can sequentially compute the ’s in decreasing numerical
order. If we substitute in the expression generating the flipped
channel, the expression for the MAC covariance matrix of the
th user in (13) can be expanded as
(15)
where the effective channel is decomposed
using the SVD as , where is a
square and diagonal matrix.
D. MIMO MAC with Individual Power Constraints
We can also obtain the capacity region of a MIMO MAC with
individual power constraints on each user from the dirty paper
region of a dual MIMO BC. By [9, Theorem 3], we can char-
acterize the individual power constraint MIMO MAC capacity
region as an intersection of sum power constraint MIMO MAC
capacity regions. By duality, we know that the sum power con-
straint MIMO MAC capacity region is equal to the dirty paper
achievable region of the dual MIMO BC.
VISHWANATH et al.: DUALITY, ACHIEVABLE RATES, AND SUM-RATE CAPACITY OF GAUSSIAN MIMO BROADCAST CHANNELS 2663
Corollary 1: The capacity region of a MIMO MAC is the
intersection of the scaled dirty paper regions of the MIMO BC.
Mathematically, this is stated as
(16)
Proof: This result can be obtained by a straightforward
application of [9, Theorem 3] to the MIMO MAC capacity re-
gion and the duality developed in Theorem 2. The scaled MIMO
BC here refers to the channel where the matrix of each receiver
is scaled by .
V. SUM RATE CAPACITY OF BC CHANNELS
In the previous sections we showed that the dirty paper re-
gion of the BC and the union of the dual MAC capacity regions
are equivalent. Now we show that the dirty paper broadcasting
strategy is the capacity-achieving strategy for the sum rate ca-
pacity of the MIMO BC. To do this, we make use of the duality
of the dirty paper region and the dual MAC to show that the dirty
paper region achieves an upper bound on the sum rate capacity
of the MIMO BC.
In [10], Sato presents an upper bound on the capacity region
of general BCs. This bound utilizes the capacity of the coop-
erative system as defined in Section II. Since the cooperative
system is the same as the BC, but with receiver coordination, the
capacity of the cooperative system is an upper
bound on the BC sum rate capacity . This
bound is not tight in general, but by introducing noise correla-
tion at the different receivers, we can get a much stronger bound.
Since the capacity region of a general BC depends only on
the marginal transition probabilities of the channel (i.e., )
and not on the joint distribution [16, Theorem
14.6.1], correlation between the noise vectors at different re-
ceivers of the BC does not affect the BC capacity region. It does,
however, affect the capacity of the cooperative system, which is
still an upper bound on the sum rate of the BC. Therefore, we
retain , as before (i.e., noise compo-
nents at the multiple receive antennas within a single receiver
are uncorrelated) and let , since intro-
ducing noise correlation within a receiver affects the broadcast
capacity region. Let denote the noise covariance matrix in the
cooperative system (i.e where ) to
define the set to be all nonsingular (or strictly positive defini-
tive) noise covariance matrices satisfying the Sato upper bound
conditions
.
.
.
.
.
.
.
.
.
(17)
Then, for any , the cooperative capacity
is an upper bound to ,
since receiver coordination can only increase capacity. Hence,
an upper bound on can be obtained as
From [2], the cooperative capacity is defined as
Using this definition, we write the Sato upper bound as
(18)
Thus, the region given by
is an upper bound on . Next, we show that the sum
rate capacity of the MIMO BC actually equals the Sato upper
bound.
Theorem 3: The sum rate capacity of the MIMO BC equals
the Sato upper bound. Furthermore, the dirty paper coding
strategy achieves the sum rate capacity of the MIMO BC
(19)
Proof: Since the sum rate capacity of the MIMO BC can
be no larger than the Sato upper bound, it is sufficient to show
that the Sato upper bound is actually achievable in the MIMO
BC using dirty paper coding. Note that, by duality, we know that
the maximum sum rate of the MIMO MAC equals the maximum
sum rate of the dirty paper achievable region. We, therefore,
must show the inequality
(20)
(21)
We prove (21) by using Lagrangian duality to express both
the Sato upper bound and the MIMO MAC sum rate capacity in
different forms. Specifically, as shown in Appendix, Section C,
we can alternatively write the Sato upper bound defined in (18)
as (see (58))
such that
(22)
and the MIMO MAC sum rate capacity (20) as
such that
(23)
Notice that the objective functions of (22) and (23) are the same,
but the variables and constraints are different. We will show
that by constructing a feasible
2664 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
solution to the Sato upper bound dual problem from an optimal
solution to the MIMO MAC sum rate dual problem.
Let be an optimizing solution to (23), i.e.,
Since (23) is a minimization of a convex function over a closed
set, we know that the minimum is achieved, so a minimizing
pair exists. We prove (21) by explicitly constructing
a feasible set of variables for the Sato upper bound
(22) such that the objective functions in (23) and (22) are equal.
Let us first consider the choice of values of as
(24)
(25)
(26)
As long as this choice of is positive definite, it can be verified
by the method used below that this set is feasible for (22) and
that the objective functions of both minimizations are the same.
Thus, we have constructed the worst case noise for the Sato
upper bound and have shown (21), but only for the case when
. However, in many practical cases, this choice of is
singular, and hence, not a feasible choice of for (22).
To circumvent this singularity, we construct, instead, a family
of feasible points (i.e., ) by introducing an arbitrary pa-
rameter . This family of values of is given by
(27)
(28)
(29)
We need to ensure that this set is feasible for (22). Since
are an optimizing solution of (23), must
satisfy the constraints in (23). Therefore, we have that
and . Since the matrix is
block diagonal and symmetric by construction, we see that if
then . We, thus, need to verify that and
that .
Note that and
(30)
Since are an optimizing solution of (23), we have
for all . This implies that
. Since , we have
(31)
This implies that . It, thus, remains to
show that . Since , we also have that .
This implies that . Since , we then get .
Hence, form a feasible set of values for (22). Since
Fig. 2. Dirty paper broadcast region: K = 2, t = 2, r = r = 1, H =
[1 :4]; H = [:4 1], P = 10.
the Sato upper bound is equal to the infimum (over the feasible
set) of the objective function, we have
(32)
Since this holds for any , we get
which completes the proof of the theorem.
A nice property of the proof of the sum rate capacity is that it
is constructive in the sense that the proof generates worst case
noise covariances for the Sato upper bound, assuming that the
optimizing solution to the MIMO MAC sum rate problem is
known. Specifically, in (29), we explicitly construct a noise co-
variance for which the cooperative capacity is larger than the
MIMO MAC sum rate capacity by an arbitrarily small amount
. Though we show that the constructed matrix when
, as noted earlier when we still are guaranteed
. If the constructed matrix with is strictly non-
singular (i.e., ), then the cooperative capacity with noise
covariance is equal to the MIMO MAC sum rate capacity.
Therefore, in these cases, is in fact a worst case noise covari-
ance for the Sato upper bound. Numerically, we also find to
be a worst case noise covariance for cases when is singular
when , as shown later in Example 2.
The dirty paper BC region and the capacity regions of the dual
MAC, along with the Sato upper bound and single-user bounds,
are illustrated for a symmetric two user channel in Fig. 2. The
dirty paper region is the union of the pentagons in the figure
because the dirty paper region is formed as a union of the indi-
vidual power constraint MAC regions. Since each receiver has
only a single antenna, the dual MIMO MAC region with in-
dividual power constraints is a simple pentagon. The capacity
upper bound is obtained by taking the intersection of the regions
formed by the two single-user optimum corner points (which are
parallel to the axes) and the Sato upper bound, which is tight at
the sum rate capacity. Note that the region formed by all three
VISHWANATH et al.: DUALITY, ACHIEVABLE RATES, AND SUM-RATE CAPACITY OF GAUSSIAN MIMO BROADCAST CHANNELS 2665
Fig. 3. Achievable region and Sato upper bound for Example 1
upper bounds is, in fact, quite close to the dirty paper achievable
region. Also note that the boundary of the dirty paper achiev-
able region has a straight-line segment at the sum rate point.
This characteristic of possessing a straight-line segment (i.e.,
a time-division portion) at sum rate is also true for the MIMO
MAC capacity region when the transmitters have more than one
antenna [4].
VI. NUMERICAL EXAMPLES
In this section, we provide two numerical examples to better
illustrate the concepts discussed in the paper.
Example 1: Consider a two-user BC with and channel
matrices
(33)
The dirty paper achievable region is very difficult to compute
without employing duality, as discussed in Section III-A. Thus,
we find the dual MAC region using convex optimization tech-
niques to obtain the achievable region in Fig. 3.
To compute the Sato upper bound for the problem, we solve
the dual problem to the MIMO MAC. Note that this problem
is a convex problem with linear matrix inequality constraints.
There are many techniques in convex optimization literature
to solve such problems. We use an easily available software
called SDPSOL, developed by Boyd and Wu [17], to get that
2.2615 nats/s and obtain to be
From these, we obtain the worst case noise (using (29) with
)
which is nonsingular. Therefore, we find that
The corresponding upper bound to the capacity region is shown
in Fig. 3.
The sum rate maximizing covariance matrices in the MAC
are
Notice that the sum rate is not maximized at a single point on
the boundary of the capacity region, but it is actually maximized
along a line segment. The corner points of this line segment are
circled in Fig. 3. In the MAC, the lower corner point of this line
segment can be achieved using the above covariance matrices
and by decoding user 1 last. The upper corner point
of the line segment can be achieved using the same covariance
matrices, but the opposite decoding order (i.e., decode user 2
last). Any other point on the line segment can be achieved by
time-sharing between these two decoding orders.
We can use the MAC–BC transformations in (8) to find the
corresponding sum rate capacity-achieving BC covariance ma-
trices. Note, however, that the transformations depend on the
decoding order in the MAC. If we assume that user 1 is decoded
last in the MAC, the transformed BC covariances are
The lower corner point of the sum rate line segment is then
achievable in the BC using these covariance matrices and by
decoding user 2 last (i.e using dirty paper coding for user 2 to
cancel out the signal of user 1). To achieve the upper corner point
of the sum rate line segment, we must perform the MAC–BC
transformations using the opposite order in the MAC. We then
get
Clearly, these BC covariance matrices are different than those
used to achieve the other corner point of the sum rate line seg-
ment. Therefore, we see that in the MAC the corner points of
the sum rate boundary can be achieved by using the same set of
covariance matrices and different decoding orders. In the BC,
however, a different decoding order and different covariance
matrices are needed to achieve the corner points of the sum rate
boundary.
Example 2: Consider a three-user BC, with two antennas
at the transmitter and one antenna each per receiver
. The channel matrices are given by
,
and the total power constraint is . Note that the channels
are unit vectors in Euclidean space, and are spaced 120 apart,
as shown in Fig. 4. Also note that the channel matrix
(34)
has rank two, and that .
2666 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
Fig. 4. Channel parameters for Example 2.
First, let us consider the dual MAC problem. By the sym-
metric structure of these channels, it is clear that allocating equal
power to each user maximizes the sum rate of this system. Thus
sum rate capacity is achieved with and
any MAC decoding order.
Using the MAC-to-BC transformations in (8), we find covari-
ances in the broadcast (corresponding to encoding user 1 last,
user 2 second, and user 3 first) that achieve the same sum rate
point on the capacity region to be
(35)
(36)
and the sum rate capacity equals
0.8109 nats/use
Now, let us find the worst case noise for the Sato upper bound.
Note that, if , then . This
implies that the received signal at one of the antennas is a linear
combination of the signal at the other two antennas. Therefore,
one receive antenna can be eliminated from the system without
any loss in the cooperative capacity. Since
, we require that . Thus, a
noise covariance matrix given by
(37)
corresponds to , which allows us to eliminate
one receive antenna. This noise covariance is a candidate for
the worst case noise covariance for the Sato upper bound. Note
that this noise covariance is singular. If we eliminate the third
antenna output, we are left with the following two-input–two-
output channel:
(38)
The cooperative capacity with this noise covariance then is
(39)
To evaluate the expression above, we use the standard water-
filling technique [2] and find the optimizing to be
The corresponding cooperative capacity is thus equal to
0.8109 nats/channel use. Since the cooperative capacity with
noise covariance equals the MIMO MAC sum rate
capacity, is a worst case noise for this problem. Now, let
us use the method for obtaining the worst case noise introduced
in the proof of Theorem 3. Using SDPSOL we get
and
From (26) we can construct the worst case noise covariance to
be
(40)
(41)
We immediately notice that . Thus, for this case,
the singular noise covariance constructed from (26) actually is a
worst case noise covariance, even though we are not guaranteed
this when the noise is singular. It may, in fact, be that the noise
covariance constructed using (26) is always a worst case noise
covariance (and not just when it is nonsingular), but we have not
been able to prove this.
VII. CONCLUSION
In this paper, we established a duality relationship between
two seemingly unrelated regions: the achievable region of the
MIMO BC obtained using the dirty paper coding and the ca-
pacity region of the MIMO MAC. This duality allows us to
easily find the dirty paper achievable region and the dirty paper
covariance matrices which achieve the boundary of this region.
Though the capacity region of the MIMO BC is unknown due to
its nondegraded nature, we were able to show that the dirty paper
achievable region achieves the sum rate capacity of the MIMO
BC through the use of the MAC–BC duality and the Sato upper
bound. These results open up the possibility that the dirty paper
region is the actual capacity region of the MIMO BC and also
the possibility that other instances of duality exist in Gaussian
multiterminal networks.
APPENDIX
A. A Covariance Matrix for Flipped Channel
Given a covariance matrix for some channel , we wish to
find a covariance matrix such that and
(42)
If the SVD of is , where is square and di-
agonal, then we propose . Using the identity
VISHWANATH et al.: DUALITY, ACHIEVABLE RATES, AND SUM-RATE CAPACITY OF GAUSSIAN MIMO BROADCAST CHANNELS 2667
and the fact that and ,
we can write the capacity of the unflipped channel as
(43)
We can similarly write the capacity of the flipped channel with
our candidate covariance matrix as
(44)
Therefore, the rate achieved by in the flipped channel is the
same as the rate achieved by the original covariance matrix
in the unflipped channel. It thus only remains to show
that . To do so, we make use of the identity
. Clearly, we can write
(45)
We then use Gram–Schmidt to expand into a full unitary ma-
trix
(46)
such that . Using this unitary matrix, we can
write
(47)
To get (47), we used the fact that the matrix is positive
semidefinite, which implies .
B. Proof of Trace Constraint for Transformations
In this section, we show that the MAC–BC transformations
obtained in (8)–(10) satisfy the sum trace requirement. First, we
compute
By adding to both sides we get
By the definition of , we get
Using this expression for we get
By induction, we can further show that
for any . For , we get
The same proof method can be used to show that the BC–MAC
transformations in (12)–(14) also satisfy the trace constraints.
C. Finding the Lagrangian Dual Problem
We first find the dual problem of the maximum sumrate of
the MIMO MAC2
(48)
over the convex set
The problem given by (48) is a convex optimization problem,
i.e., it has a concave objective function and a convex constraint
set. Hence, a convex Lagrangian dual minimization problem can
be obtained that achieves the same optimum value at (48). For
this, we rewrite (48) as
such that
Note that matrix inequalities are associated with dual variables
that are matrices, while scalar inequalities are associated with
scalar dual variables. The Lagrangian for this problem is
(49)
2This derivation is based on the dual problem found in [4]
2668 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
The dual function is found by minimizing with respect to the
primal variables
(50)
We obtain the optimality conditions by differentiating the La-
grangian (49) with respect to the primal variables to get
For any Lagrangians not satisfying these conditions, we get
. For Lagrangians that do satisfy these con-
ditions, we get
(51)
The dual problem is then obtained by maximizing the dual func-
tion with respect to the dual variables
such that
(52)
Due to the convexity of the original optimization, the sum rate
capacity of the MAC is equal to the solution of the dual problem
above (52).
We now use Lagrangian duality to find an alternative form
for the Sato upper bound. The Sato upper bound is originally
defined in (18) as
(53)
We will find an alternate form for this upper bound by consid-
ering the Lagrangian dual of only the inner maximization (and
not of the entire expression). For some fixed , consider
the inner maximization
(54)
Note that the maximization in (54) is the capacity of a mul-
tiple-antenna system with a channel given by and ad-
ditive white Gaussian noise [2]. The capacity of a system with
the conjugate transpose channel can be shown to be
exactly equal to that in (48) (see [2] for proof). Therefore, (54)
is equivalent to
(55)
Notice that this maximization is equivalent to the form
of the MAC sumrate maximization in (48) with ,
, and . Therefore, the maximization
(55) is equivalent to
such that
(56)
Clearly, we can multiply the last inequality by the term
on both sides and negate the objective function to get
such that
(57)
Since this is equivalent to the inner maximization of the Sato
upper bound for every , we can rewrite the Sato upper
bound as
such that
(58)
ACKNOWLEDGMENT
The authors wish to thank Syed A. Jafar for helpful discus-
sions regarding singular noise covariances.
REFERENCES
[1] G. J. Foschini and M. J. Gans, “On limits of wireless communications in
a fading environment when using multiple antennas,” Wireless Personal
Commun., vol. 6, pp. 311–335, 1998.
[2] E. Telatar, “Capacity of multi-antenna Gaussian channels,” European
Trans. Telecomm., vol. 10, no. 6, pp. 585–596, Nov. 1999.
[3] S. Verdú, “Multiple-access channels with memory with and without
frame synchronism,” IEEE Trans. Inform. Theory, vol. 35, pp. 605–19,
May 1989.
[4] W. Yu, W. Rhee, S. Boyd, and J. Cioffi, “Iterative water-filling for vector
multiple access channels,” in Proc. IEEE Int. Symp. Information Theory,
Washington, DC, June 24–29, 2001, p. 322.
[5] G. Caire and S. Shamai, “On achievable rates in a multi-antenna broad-
cast downlink,” in Proc. 38th Annu. Allerton Conf. Communication,
Control and Computing, Monticello, IL, Oct. 4–6, 2000.
[6] M. Costa, “Writing on dirty paper,” IEEE. Trans. Inform. Theory, vol.
IT-29, pp. 439–441, May 1983.
[7] G. Caire and S. Shamai (Shitz), “On the achievable throughput of a
multiantenna Gaussian broadcast channel,” IEEE Trans. Inform. Theory,
vol. 49, pp. 1691–1706, July 2003.
[8] W. Yu and J. Cioffi, “Trellis precoding for the broadcast channel,” in
Proc. IEEE Global Telecommunications Conf. (GLOBECOM), Nov.
2001, pp. 1344–1338.
[9] N. Jindal, S. Vishwanath, and A. Goldsmith, “On the duality of mul-
tiple-access and broadcast channels,” in Proc. Allerton Conf. Communi-
cations, Control, and Computing, Oct. 3–5, 2001. Full version submitted
to IEEE Trans. Inform. Theory.
[10] H. Sato, “An outer bound on the capacity region of broadcast channel,”
IEEE. Trans. Inform. Theory, vol. IT-24, pp. 374–377, May 1978.
[11] W. Yu and J. Cioffi, “Sum capacity of a Gaussian vector broadcast
channel,” in Proc. IEEE Int. Symp. Information Theory, Lausanne,
Switzerland, June 30–July 5 2002, p. 498.
[12] P. Viswanath and D. N. C. Tse, “Sum capacity of the vector Gaussian
broadcast channel and uplink–downlink duality,” IEEE Trans. Inform.
Theory, vol. 49, pp. 1912–1921, Aug. 2003.
[13] S. Vishwanath, G. Kramer, S. Shamai, S. Jafar, and A. Goldsmith,
“Outer bounds for multi-antenna broadcast channels,” in Proc. DIMACS
Workshop on Signal Processing for Wireless Transmission, Rutgers,
New Brunswick, NJ, Oct. 2002.
[14] D. Tse and P. Viswanath, “On the capacity of the multiple antenna broad-
cast channel,” in Proc. DIMACS Workshop on Signal Processing for
Wireless Transmission, Rutgers, NJ, October 2002.
[15] E. Jorswieck and H. Boche, “Rate balancing for the multi-antenna
Gaussian broadcast channel,” in Proc. IEEE Int. Symp. Spread Spectrum
Techniques and Applic., 2002, pp. 545–549.
[16] T. Cover and J. Thomas, Elements of Information Theory. New York:
Wiley, 1991.
[17] L. Vandenberghe, S. Boyd, and S. P. Wu, “Determinant maximization
with linear matrix inequality constraints,” SIAM J. Matrix Anal. Appl.,
vol. 19, no. 2, pp. 499–533, 1998.
[18] S. Vishwanath, N. Jindal, and A. Goldsmith, “On the capacity of mul-
tiple input multiple output broadcast channels,” in Proc. IEEE Int. Conf.
Commun., New York, Apr. 2002.
[19] N. Jindal, S. Vishwanath, and A. Goldsmith, “On the duality of multiple-
access and broadcast channels,” in Proc. IEEE Int. Symp. Information
Theory, Lausanne, Switzerland, June 30–July 5 2002, p. 500.

欢迎咨询51作业君