Multiuser Receivers, Random Matrices and

Free Probability

David N.C. Tse
Department of Electrical Engineering and Computer Sciences
University of California
Berkeley, CA 94720, USA
[email protected]
There are often curious and deep connections between engineering and mathematics. We
tell one such story here. It starts with the engineering problem of capacity analysis of direct-
sequence spread spectrum wireless networks. Using results from convergence of spectra of
large random matrices, we obtain simple answers for a basic model of this problem, in terms of
notions of eective bandwidths and eective interference. In the process of understanding the
structure of our solution better, we stumble on free probability, a theory for non-commutative
random variables. We establish a striking connection between certain basic results in this
theory and the concept of eective interference. Using free probability as a new tool, we
are in turn able to analyze more complex models for the original wireless communications
problem. Our story has come a full circle.
1 The Problem
With the introduction of the IS-95 Code-Division Multiple-Access (CDMA) standard, the use
of spread-spectrum as a multiple-access technique in commercial wireless systems is growing
rapidly in popularity. Unlike more traditional methods such as time-division multiple access
(TDMA) or frequency-division multiple access (FDMA), spread-spectrum techniques are
broadband in the sense that the entire transmission bandwidth is shared between all users at
all times. This is done by the spreading of the users signals onto a bandwidth much larger
than an individual users information rate. The advantages of spread-spectrum techniques
include simpler statistical multiplexing without explicit scheduling of time or frequency slots,
universal frequency reuse between cells, graceful degradation of quality near congestion, and
exploitation of frequency-selective fading to avoid the harmful eects of deep fades that
aict narrowband systems.

This research is supported by a National Science Foundation Early Faculty CAREER Award.
1
One form of spread-spectrum is direct-sequence CDMA. In this multiple access method, each
user is assigned a signature sequence on which it modulates its data. A simple channel model
for such a system is:
y =
K

k=1
x
k
s
k
+w
N
, (1)
where K is the number of users, x
k
the transmitted data symbol of user k, w N(0,
2
I
N
)
is the additive Gaussian noise in the channel, and y is the received vector. We assume that
E[x
k
] = 0, E[x
2
k
] = p
k
, the received power of user k. The parameter N, sometimes called
the processing gain, is the ratio of the channel bandwidth and the data symbol rate and
quanties the amount of spreading in the system. The larger the channel bandwidth, the
larger N can be. Geometrically, communication takes place in a signal space of dimension
N, with each user occupying a signal direction dened by its signature sequence s
k
. The
parameter N can also be thought of as the number of degrees of freedom in the system.
The task of a receiver is to estimate the data symbol of each of the users from the received
vector y. We assume that the receiver has knowledge of the signature sequences and received
powers of the users.
A natural class of receivers are the linear receivers. Focusing on user 1, the estimate x
1
of the
transmitted symbol x
1
is of the form x
1
= c
t
1
y, where c
1

N
is the linear receiver for user
1. For example, choosing c
1
= s
1
yields the well-known matched-lter receiver; it projects
the received signal onto the direction of the signature sequence of user 1. This is the receiver
used in current-generation CDMA systems, and is simple in the sense that the receiver needs
only keep track of the signature sequence of user 1 and not the others. However, one can
expect that better performance can be attained by taking advantage of the knowledge of the
signature sequences and received powers of other users as well.
A commonly used measure to evaluate the performance of linear receivers is the output
signal-to-interference ratio:
SIR
1
:=
(c
t
1
s
1
)
2
p
1
(c
t
1
c
1
)
2
+

i=1
(c
t
1
s
i
)
2
p
i
This is simply the ratio of the variance of user 1s signal to the variance of noise plus
interference from other users, measured at the output of the linear receiver. It is not too
dicult to show that the optimal receiver which maximizes the output SIR is the minimum
mean-square error (MMSE) receiver which minimizes E[( x
1
x
1
)
2
]. This is the classic least
squares problem and has a well-known solution. The MMSE receiver and its SIR performance
is given by:
c
1
= (SDS
t
+
2
I)
1
s
1
SIR
1
= p
1
s
t
1
(SDS
t
+
2
I)
1
s
1
(2)
where
S := [s
2
, . . . , s
K
] , D := diag (p
2
, . . . , p
K
) . (3)
The MMSE receiver is an example of a multiuser receiver which, in contrast to the con-
ventional matched lter, exploits the information about the other users to mitigate their
interference.
The capacity analysis problem is this: given users each with its own target SIR requirement,
nd the mix of users that can be admissible under the MMSE receiver. This problem is
currently relevant in the design of future-generation wireless systems. The capability of
multiuser receivers needs to be better understood to assess whether the performance gain
over the conventional receiver warrants the additional complexity in implementation.
2 The Solution
Although (2) gives a formula for the SIR of the MMSE receiver, the complicated dependence
on the signature sequences and received powers of the users makes it dicult to be used
directly for capacity analysis. Moreover, the performance certainly depends on which specic
sequences are used. We bypass these drawbacks by instead using a random signature sequence
model. The entries of s
i
s are modeled as i.i.d. zero-mean random variables, with variance
normalized to be 1/N, and are also independent across users. This model provides analytical
tractability, and it is often a reasonable approximation in practice as the wireless multipath
channel typically randomizes the sequences of the users. Moreover, many CDMA systems
use pseudorandom spreading sequences. It should also be noted that the random sequence
model is used only for performance analysis purpose; from the point of view of the receiver,
the assumption of perfect knowledge of (the realization of) the signature sequences is still
retained. In practice, this information is obtained through an adaptive tracking algorithm.
In this model, SIR
1
is a random variable, being a function of the random sequences. The
following is the key result, showing that in a large system, SIR
1
converges to a deterministic
constant. To simplify the notation, we set p
1
= 1 without loss of generality.
Theorem 1 [1] Let N, K such that
K
N
, and assume that the empirical distribution
of the users powers converges to a limiting distribution F. Then SIR
1
converges in probability
to

, where

is the unique solution to the xed-point equation:

=
1

2
+
_

0
I(p,

)dF(p)
where
I(p, x)
p
1 +px
Here, is the system loading in terms of number of users per degree of freedom. Heuristically,
the result says that in a large system,
SIR
1

1

2
+
1
N

K
k=2
I(p
k
, SIR
1
)
Although in general this xed-point equation has no closed-form solution, it can be shown
that the xed point can be computed numerically by simply iterating from any initial point.
More importantly, if user 1 has a target SIR requirement , then it follows from the mono-
tonicity of the xed-point equation that its SIR requirement is satised asymptotically if
and only if

1

2
+
1
N

K
k=2
I(p
k
, )
. (4)
This condition can be checked explicitly.
It is natural to dene I(p, ) as the eective interference of an interferer with received power
p on a user with a target SIR . This summarizes succinctly the eect of an interferer. It
is interesting to contrast this to the corresponding result for the matched lter receiver [1]:
the eective interference under the matched lter is simply I
mf
(p) = p. Note that under the
matched lter, the eect of an interferer is proportional to its received power. In contrast,
under the MMSE receiver, the eect is highly nonlinear in the received power, and ceiling out
at
1

. This is a testimony to the interference suppression capability of the MMSE receiver.

j=1

j
1 +
j
min
1jJ
_
1

j

2
p
j
_
.
The set of class mixes (
1
, . . . ,
J
) of users that can be simultaneously supportable is the
capacity region of the system. The above equation says that the capacity region admits a
simple description via a single linear constraint. When there are no power constraints, the
right hand side simplies to 1.
It is now natural to dene the eective bandwidth of a user with target SIR requirement of
:
e() =

1 +
.
This is the fraction of a degree of freedom occupied by the user. To compute the admissi-
bility of a set of users, one only needs to add up the eective bandwidths of the individual
users. The additivity of eective bandwidths follows from the decoupling of the aggregate
interference eect into the eective interference of the individual interferers.
Two curious questions arise at this point:
Why does the SIR converge to a deterministic limit independent of the random signa-
ture sequences?
Why does the interfering eects of the users decouple in such a simple way?
We investigate these two questions in the following sections.
3 Random Matrices
Recall that the SIR of user 1 (with unit received power) is given by:
SIR
1
= s
t
1
(SDS
t
+
2
I)
1
s
1
(5)
where S and D are dened in eqn. (3). Observe that S depends only on the signature
sequences of the interferers and is hence independent of s
1
. Direct computation yields:
E[SIR
1
|S, D] =
1
N
Tr
_
SDS
t
+
2
_
1
.
Moreover, it can be shown that the conditional variance goes to zero like 1/N. Hence,
SIR
1

1
N
Tr
_
SDS
t
+
2
_
1 P
0. (6)
We can write:
1
N
Tr
_
SDS
t
+
2
I
_
1
=
_

0
1
+
2
dG
N
() (7)
where has the (random) empirical eigenvalue distribution of SDS
t
. Thus, the convergence
of the SIR hinges on the convergence of the spectrum G
N
. This problem has been solved by
[2, 3], where they show that the limit exists and moreover does not depend on the distribution
of the individual elements of S. The limiting spectrum is described by a functional xed-
point equation for its Steltjes transform. The Steltjes transform of a distribution G is dened
to be:
m(z) :=
_
1
z
dG()
The functional xed-point equation for the Steltjes transform m

(z) of the limiting spectrum

of SDS
t
is given by:
m(z) =
1
z +
_
dF()
1+m(z)
(8)
where F is the limiting spectrum of D.
This seems like a complicated characterization of the limiting spectrum. However, we observe
from (6) and (7) that what we need to characterize the limiting SIR is precisely the Steltjes
transform of the limiting spectrum of SDS
t
evaluated at z =
2
. Theorem 1 now follows.
4 Free Probability
The eective interference interpretation follows directly from the random matrix result (8).
Let us then take a deeper look at the structure of this equation from a dierent perspective.
Consider the scenario when there are two groups of interferers C
1
and C
2
, one in which the
interferers have common received power p and one in which the interferers have common
received power q respectively. Suppose there are K
1
users in group C
1
and K
2
users in group
C
2
, with K
1
/N =
1
and K
2
/N =
2
. The key random matrix SDS
t
can be written as an
outer sum:
SDS
t
= p

iC
1
s
i
s
t
i
+q

iC
2
s
i
s
t
i
U
1
+U
2
.
The asymptotic interfering eect of each group C
i
, when present in isolation, depends only
on the spectrum of the random matrix U
i
. How the overall interfering eect of the two
groups can be decoupled into the eects of the individual groups is then a question of how
the spectrum of the matrix U
1
+ U
2
depends on the individual spectra of the matrices U
1
and U
2
. This leads to a more general question: if we are given the spectra of two random
matrices A and B, what can we say about the spectrum of the sum A +B?
For deterministic matrices A and B, one cannot in general determine the eigenvalues of
A + B from those of A and of B alone, as they depend on the eigenvectors of A and B as
well. However, it turns out that for large random matrices A and B satisfying a property
called freeness, the limiting spectrum of A+B can indeed be determined from the individual
spectra of A and B. This is a central result in free probability theory, which we very briey
introduce now. For more details, please consult [4] or [5].
Classical probability theory is concerned with commutative random variables. Free prob-
ability, on the other hand, deals with non-commutative ones. More formally, a (non-
commutative) probability space (A, ) is an algebra A over C with an unit element 1 and
endowed with a linear functional, called the trace, : A C, (1) = 1. Elements of A are
called (non-commutative) random variables. Classical probability theory is obtained when
the algebra A consists of scalar random variables and the functional is the standard ex-
pectation operator. The focus of the theory however is on random variables which do not
commute.
The distribution of a random variable X A is specied by the moments (X
k
), for k 1.
The distribution dened in this form allow us to compute the expectation of any function
of the random variable X that can be approximated by polynomials. Similarly, the joint
distribution of a collection of random variables X
1
, . . . , X
m
A is specied by all the joint
moments (X
i
1
. . . X
ip
), p 1.
The central notion in classical probability theory is independence. In the notations introduced
above, two scalar random variables X, Y are independent if (X
k
Y
l
) = (X
k
)(Y
l
) for all
k, l. The analogous notion in free probability theory is freeness.
Denition 2 Let X and Y be two random variables. Let A
1
be the sub-algebra generated
by X and the unit 1 and A
2
be the sub-algebra generated by Y and the unit 1 respectively,
i.e. they consist of polynomials of X and of Y respectively. The random variables X and Y
are free if (Z
1
. . . Z
m
) = 0 whenever (Z
k
) = 0 for all k = 1, . . . , m and Z
k
A
i(k)
where
consecutive indices i(k) = i(k + 1) are distinct.
For independent random variables, the joint distribution can be specied completely by the
marginal distributions. For free random variables, the same result can be proved, directly
from denition. In particular, if X and Y are free, then the moments ((X +Y )
n
) of X +Y
can be completely specied by the moments of X and the moments of Y . The distribution is
naturally called the free convolution of the two marginal distributions. Classical convolution
can be computed via transforms: the log moment generating function of the distribution of
X + Y is the sum of the log moment generating functions of the individual distributions.
For free convolution, the appropriate transform is called the R-transform. This is dened
via the Steltjes transform.
Given a random variable X, let
m
X
(z) = E
_
1
X z
_
be the Stieltjes transform of its distribution. Let m
1
X
be the inverse of m
X
. The R-transform
is dened as:
R() :=
1

+m
1
X
().
Theorem 3 If X and Y are two free random variables, then R
A+B
= R
A
+R
B
.
A good example of non-commutative random variables are random matrices. Let A = M
N
be the algebra of complex N by N random matrices whose entries are scalar random variables
dened on some underlying common probability space. The trace is dened as:

N
(X) :=
1
N
E [TrX] .
For any N by N random Hermitian matrix X M
N
with random eigenvalues
1
, . . .
N
, the
rth moment of X in the non-commutative probability space (M
N
,
N
) is given by

N
(X
r
) =
1
N
E[TrX
r
] =
1
N
E
_
N

i=1

r
i
_
If we let F
X
() be the expected empirical distribution of the eigenvalues of X:
F
X
() :=
1
N
E [|{i :
i
}|]
then the moments of the distribution F
X
are precisely the moments of X as a non-commutative
random variable.
The deep connection between random matrices and free probability is rst made by Voiculescu
[6], who showed that in a lot of cases of interest, large random matrices become asymptot-
ically free. This answers the question we posed earlier: the limiting spectra of the sum of
two large random matrices is the free convolution of the limiting spectra of the individual
matrices, if they become asymptotically free.
Returning to our specic problem, it can be shown as a consequence of Voiculescus results
that the matrices U
1
= p

iC
i
s
i
s
t
i
and U
2
=

iC
2
s
i
s
t
i
are in fact asymptotically free as
N, K , K/N . . The R-transforms can be computed explicitly for this problem:
R
U
1
() =
1
p
1 +p
, R
U
2
() =
2
q
1 +q
,
and
R
U
1
+U
2
() = R
U
1
() +R
U
2
().
What is the connection of this to the notion of eective interference? Observe that the
R-transform satises:
m(z) =
1
z +R[m(z)]
.
Putting in z =
2
and noting that m(
2
) is the limiting SIR, we conclude that at
target SIR requirement of , R
U
i
(), i = 1, 2, is the eective interference of group C
i
when
considered in isolation, and R
U
1
+U
2
() is the limiting aggregate interference of the two groups
when both are present. The decoupling of eective interference is nothing but the
additivity of the R-transforms of free random matrices.
5 Back to Multiuser Receivers
The previous section re-interprets the structure of the xed-point equation in Theorem 1 in
terms of notions from free probability. The proof of Theorem 1 itself does not require free
probability, as the structure of the relevant random matrix SDS
t
is a classical one for which
a limit theorem already exists. However, the analysis of more sophisticated CDMA models
[7, 8] led to non-classical random matrix structure, for which new limit theorems had to be
proved. Free probability is a valuable tool for solving these problems. We discuss one such
problem here [8].
One detrimental eect of a wireless link is the random fading of the channel due to con-
structive and destructive interference between multiple signal paths from the transmitter
to the receiver. A countermeasure to alleviate this problem is the use of multiple antennas
at the receiver. Provided that the antennas are placed suciently far apart, the received
signals at the antennas fade independently and the probability is high that at least one of
the antennas receives a strong copy of the transmitted signal. The following is a model of a
direct sequence CDMA system with 2 receive antennas:
y(l) =
K

k=1

k
(l)x
k
s
k
+w(l) C
N
, l = 1, 2.
where as before, x
k
, s
k
are the transmitted symbol and signature sequence of the kth user
respectively, y(l) is the received signal at antenna l, and
k
(l) is the random channel gain
from user k to an antenna l.
As in the basic model, we can consider the MMSE estimator for transmitted symbol x
1
,
based now on y(1) and y(2), the received signals at both of the antennas. In place of SDS
t
for the basic model, the key random matrix for this problem is

S

S

, where

S =
_
SB
1
SB
2
_
and S = [s
2
. . . s
k
] and B
l
= diag(
2
(l), . . . ,
K
(l)).
There is strong dependency between entries in the random matrix

S, due to the repetition of
the signature sequences at the two receive antennas. Existing results on spectral convergence
do not apply. However, we observe that

S

S

and

S

S have the same nonzero eigenvalues,
and the latter can be written as a sum of two matrices:

S = B

1
S
t
SB
1
+B

2
S
t
SB
2
We have the following theorem.
Theorem 4 [1] If B
1
, B
2
are independent and zero mean, then the matrices B

1
S
t
SB
1
and
B

2
S
t
SB
2
are asymptotically free as N, K , K/N = .
Moreover, it can be shown that if S
1
and S
2
are two independent matrices, each having the
same distribution as S, then B

1
S
t
1
S
1
B
1
and B

2
S
t
2
S
2
B
2
are also asymptotically free. The
implication is that the limiting spectrum of

S
t

S is the same as if independent copies of the
signature sequences were received at the dierent antennas. For this latter independent
sequence model, existing random matrix results can be applied and the performance of the
MMSE receiver can be analyzed. More details can be found in [9] in these proceedings. The
main point to be made here is that the important notion is freeness and not independence:
although there is strong dependence between the entries of the matrix

S, the randomness in
D
1
and D
2
is enough to make the components free. This result translates into the engineering
conclusion that there is asymptotically no loss of degrees of freedom for communication even
though the signature sequences are repeated at each of the receive antennas.
6 Conclusions
In this paper, we develop interesting connections between the engineering problem of capac-
ity analysis of multiuser receivers on the one hand, and random matrices and free probability
theory on the other. The connections are unexpected and deep. Is there anything funda-
mental relating the least square estimation problem and free probability, or is the connection
purely coincidental? The reader is encouraged to look further.
References
[1] D. Tse and S. Hanly, Linear multiuser receivers: Eective interference, eective band-
width and capacity, IEEE Trans. Inform. Theory, vol. 45, pp. 641657, Mar. 1999.
[2] V. A. Marcenko and L. A. Pastur, Distribution of eigenvalues for some sets of random
matrices, Math. USSR-Sb., vol. 1, pp. 457483, 1967.
[3] J. W. Silverstein and Z. D. Bai, On the empirical distribution of eigenvalues of a class
of large dimensional random matrices, Journal of Multivariate Analysis, vol. 54, no. 2,
pp. 175192, 1995.
[4] D. V. Voiculescu, K. J. Dykema, and A. Nica, Free Random Variables. CRM Monogragh
Series, Volume 1, Providence, Rhode Island, USA: American Mathematical Society, 1992.
[5] D. Voiculescu, Lectures on free probability theory, 1998. Notes for a Course at the
Saint-Flour Summer School on Probability Theory (unpublished).
[6] D. Voiculescu, Limit laws for random matrices and free products, Inventiones mathe-
maticae, vol. 104, pp. 201220, 1991.
[7] J. Evans and D. Tse, Linear multiuser receivers for multipath fading channels, Sub-
mitted to IEEE Trans. Inform. Theory, 1999.
[8] S. Hanly and D. Tse, Resource pooling and eective bandwidths in CDMA systems with
multiuser receivers and spatial diversity, Submitted to IEEE Trans. Inform. Theory,
1999.
[9] S. Hanly and D. Tse, Resource pooling and eective bandwidths for CDMA antenna
arrays, in Proc. Allerton Conference on Communications, Computing and Control, Mon-
ticello, Illinois, Sept. 1999.