Power Electrical Engineering

ISlT ****, Yokohama, Japan, June ** -July *, ****

Sum Power Iterative Waterfilling for Gaussian Vector Broadcast Channels

S riram Vishwanath*, Wonjong R heet, Nihar Jindal, Syed Jafar* a nd Andrea G oldsmith*

*Dept. of Electrical Engineering, tArrayComm Inc.

Stanford, CA 94305. San Jose, CA.

{sriram,njindal,syed,andrea}@wsl.stanford.edu, abqct0@r.postjobfree.com

Abstract- We obtain an eMJcient algorithmfor computing the 3. Treating these effective channels as parallel, non-interfering

sum capacity of vector broadcast channel. This algorithm utilizes channels, obtain covariance matrices Mi by waterfilling with

the duality between broadcast and multiple access channels and total power P.

the Kuhn-Tucker conditions of sum power multiple access chan-

nel.

O:,,

c

over the set A; 2 T r(A;) = P

I. I NTRODUCTION This maximization is equivalent to waterfilling the block diag-

onal channel with diagonals equal to Hjeff.

A vector broadcast channel is a one-to-many channel, where the

4. Compute the new S;(Z) = ! 2-i)si(1-1)+Mi(1)

channel between the central transmitter and the receiver i out of K for all a.

K

receivers is given by matrix H ;. Mathematically, such a channel is 5 . Return to Step 2 until desired accuracy is reached.

+

given by y; = H;x na, where y; and n; are respectively the re-

111. CONVERGENCE AND OPTIMALITY

ceived signal vector and the additive Gaussian noise vector at receiver

Here, we provide an outline for convergence and optimality. First,

i, and 2 is the transmitted signal vector.

convergence is considered. Define function f as below:

Recently, an achievable region of this channel, known as the dirry

paper region, was characterized [ I], and the region was shown to

achieve sum capacity by many research groups simultaneously (See

Then, the following can be shown.

joumal version of [ l ] and the references therein). The dirty paper

characterization in [ l] is in terms of transmit covariance matrices

E1, where Qi corresponds to user i. This characterization,

however, tums out to be non-convex in {&a}. In this paper, our aim is

to find an efficient algorithm to compute the optimal {Q;} such that

the sum capacity of the broadcast channel can be computed.

Simultaneously, a duality result was obtained in [2] showing that

the capacity region of the vector multiple access channel (MAC) with

sum power constraint on the transmitters is equal to the dirty pa-

+M K (I)

. .. ( K- 1 ) S K ( 2 - 1)

per achievable region. Moreover, an explicit transformation connects

?

K

the optimal transmission scheme for the MAC with the {Q;} above.

Thus, we obtain an efficient algorithm to solve the convex dual MAC The inequality given by Equation (2) is due to the optimality of

problem given by single-user waterfilling in step 3, and the inequality given by Equation

(3) is due to the concavity o f f and Jensen s inequality. Jensen s

I

inequality guarantees a strict increase of the function value when

any of S,(l) is different from S,(l - 1 ). Therefore, the function

value monotonically increases. However, the function value is up-

per bounded, and we can conclude that the algorithm converges to a

and then transform the solution using duality to obtain {Q;}. An

fixed point. Note that no loop can exist due to the strict inequality for

algorithm to compute the optimal transmit policy for a MAC with

S;(Z) # S;(Z - 1 . )

per-user power constraints on the transmitters was obtained in [3].

Also, 5;can be shown to converge to an optimal point. Due to the

However, this algorithm cannot be directly applied to the dual MAC

concavity of the problem, Kuhn-Tucker conditions are necessary and

due to the difference in the power constraint.

sufficient for optimality. The Kuhn-Tucker conditions can be derived

in a similar way as i n [3], and can be shown to be satisfied by the

11. T HEA LGORITHM limit of { S i } due to steps 2 and 3 of the algorithm.

The iterative algorithm converges to a fixed point which satisfies R EFERENCES

[ I] G. Caire and S . Shamai, On the Achievable Throughput of a Multi-

the Kuhn-Tucker conditions of ( l), and hence obtains the solution.

antenna Gaussian Broadcast Channel, Proc. IEEE Intl. Symp. Inform.

L et S,(l) denote the Z th iteration of Sa. Then the algorithm can be

Theory, ISIT 2001, Washington D.C., June 2001. Also submitted to the

summarized as follows:

IEEE Trans. Inform. Theory.

[2] S . Vishwanath, N. Jindal and A. Goldsmith, Sum Capacity of Multi-

1. Initialize covariance matrices to zero: S = 0 V i.

i0

Antenna Gaussian Broadcast Channels, Proc. IEEE Intl. Conf. Com-

+ mun., 2001.

=Hj(I

2. For iteration 2 : Generate e fective channels H

i

[3] W. Yu, W. Rhee, S . Boyd and J. Cioffi, Iterative Water-filling for Vector

Multiple Access Channels, IEEE Intl. Symp. Inform. Theory, (ISIT),

2001.

OThis work was supported by a Stanford Graduate Fellowship

467

0-7a03-772a-11031$17.00 IEEE.

02003

Contact this candidate