1570 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 51, NO. 4, APRIL 2005
k
bb
b
0
opt
k
1
. Suppose that there exists a vector
hh
h
that meets Conditions 1)
and 2) of Theorem 5. It is clear that this vector
hh
h
is dual feasible, and
furthermore
Re
h
ss
s
;hh
h
i
=Re
h
8
bb
b
0
opt
;hh
h
i
=Re
h
bb
b
0
opt
;
8
3
hh
h
i
=Re
h
bb
b
0
opt
;
sgn
bb
b
0
opt
i
=
k
bb
b
0
opt
k
1
:
To see that
bb
b
0
opt
uniquely solves (2), observe that the third equality can
hold only if the support of
bb
b
opt
equals
3
opt
.
A
CKNOWLEDGMENT
The author wishes to thank both anonymous referees for their in-
sightful remarks.
R
EFERENCES
[1] J. A. Tropp, “Greed is good: Algorithmic results for sparse approxima-
tion,” IEEE Trans. Inf. Theory, vol. 50, no. 10, pp. 2231–2242, Oct. 2004.
[2] S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition
by basis pursuit,” SIAM J. Sci. Comput., vol. 20, no. 1, pp. 33–61, 1999.
[3] D. L. Donoho and X. Huo, “Uncertainty principles and ideal atomic de-
composition,” IEEE Trans. Inf. Theory, vol. 47, no. 7, pp. 2845–2862,
Nov. 2001.
[4] M. Elad and A. M. Bruckstein, “A generalized uncertainty principle and
sparse representation in pairs of bases,” IEEE Trans. Inf. Theory, vol. 48,
no. 9, pp. 2558–2567, Sep. 2002.
[5] D. L. Donoho and M. Elad, “Maximal sparsity representation via
`
minimization,” Proc. Natl. Acad. Sci., vol. 100, pp. 2197–2202, Mar.
2003.
[6] R. Gribonval and M. Nielsen, “Sparse representations in unions of
bases,” IEEE Trans. Inf. Theory, vol. 49, no. 12, pp. 3320–3325, Dec.
2003.
[7] J.-J. Fuchs, “On sparse representations in arbitrary redundant bases,”
IEEE Trans. Inf. Th., vol. 50, no. 6, pp. 1341–1344, Jun. 2004.
[8] R. Gribonval and M. Nielsen, “On the Exponential Convergence of
Matching Pursuits in Quasi-Incoherent Dictionaries,” Université de
Rennes I, Rennes, France, IRISA Rep. 1619, 2004.
Sum Power Iterative Water-Filling for Multi-Antenna
Gaussian Broadcast Channels
Nihar Jindal, Member, IEEE, Wonjong Rhee, Member, IEEE,
Sriram Vishwanath, Member, IEEE, Syed Ali Jafar, Member, IEEE,
and Andrea Goldsmith, Fellow, IEEE
Abstract—In this correspondence, we consider the problem of max-
imizing sum rate of a multiple-antenna Gaussian broadcast channel
(BC). It was recently found that dirty-paper coding is capacity achieving
for this channel. In order to achieve capacity, the optimal transmission
policy (i.e., the optimal transmit covariance structure) given the channel
conditions and power constraint must be found. However, obtaining the
optimal transmission policy when employing dirty-paper coding is a
computationally complex nonconvex problem. We use duality to trans-
form this problem into a well-structured convex multiple-access channel
(MAC) problem. We exploit the structure of this problem and derive
simple and fast iterative algorithms that provide the optimum transmis-
sion policies for the MAC, which can easily be mapped to the optimal
BC policies.
Index Terms—Broadcast channel, dirty-paper coding, duality, multiple-
access channel (MAC), multiple-input multiple-output (MIMO), systems.
I. I
NTRODUCTION
In recent years, there has been great interest in characterizing
and computing the capacity region of multiple-antenna broadcast
(downlink) channels. An achievable region for the multiple-antenna
downlink channel was found in [3], and this achievable region was
shown to achieve the sum rate capacity in [3], [10], [12], [16],
and was more recently shown to achieve the full capacity region in
[14]. Though these results show that the general dirty-paper coding
strategy is optimal, one must still optimize over the transmit covari-
ance structure (i.e., how transmissions over different antennas should
be correlated) in order to determine the optimal transmission policy
and the corresponding sum rate capacity. Unlike the single-antenna
broadcast channel (BC), sum capacity is not in general achieved by
transmitting to a single user. Thus, the problem cannot be reduced
to a point-to-point multiple-input multiple-output (MIMO) problem,
for which simple expressions are known. Furthermore, the direct
optimization for sum rate capacity is a computationally complex
Manuscript received July 21, 2004; revised December 15, 2004. The work
of some of the authors was supported by the Stanford Networking Research
Center. The material in this correspondence was presented in part at the Inter-
national Symposium on Information Theory, Yokohama, Japan, June/July 2003,
and at the Asilomar Conference on Signals, Systems, and Computers, Asilomar,
CA , Nov. 2002. This work was initiated while all the authors were at Stanford
University.
N. Jindal is with the Department of Electrical and Computer Engineering,
University of Minnesota, Minneapolis, MN 55455 USA (e-mail: nihar@ece.
umn.edu).
W. Rhee is with the ASSIA, Inc., Redwood City, CA 94065 USA (e-mail:
wonjong@dsl.stanford.edu).
S. Vishwanath is with the Department of Electrical and Computer Engi-
neering, University of Texas, Austin, Austin, TX 78712 USA (e-mail: sriram@
ece.utexas.edu).
S. A. Jafar is with Electronic Engineering and Computer Science, University
of California, Irvine, Irvine, CA 92697-2625 USA (e-mail: syed@ece.uci.edu)
A. Goldsmith is with the Department of Electrical Engineering, Stan-
ford University, Stanford, CA 94305-9515 USA (e-mail: andrea@systems.
stanford.edu).
Communicated by M. Medard, Associate Editor for Communications.
Digital Object Identifier 10.1109/TIT.2005.844082
0018-9448/$20.00 © 2005 IEEE
