CDMA Codeword Optimization: interference avoidance and convergence via class warfare

Christopher Rose

KEYWORDS: Codeword optimization, codeword adaptation, adaptive modulation, interference avoidance

Contents

1  Introduction

Interference avoidance has been identified as a method to iteratively obtain optimal signature waveforms (codewords) in multiple access systems [1,2,3,4,5]. The notion behind interference avoidance is that each user, with feedback from the receiver, is allowed to adjust its waveform to minimize interference. Empirically speaking, sequential iterative updates by all users always results in a set of codewords which maximize various measures of system capacity [6,7,8] and minimize a measure of mutual interference called the total square correlation (TSC). There are even analytic hints that interference avoidance should always converge to an optimal ensemble [3]. Unfortunately, even copious empirical evidence where never has a suboptimal set been obtained starting from random codewords [1,2,3,4,5] and strong analytic hints are unsettling and hamper work which depends on provable convergence of greedy interference avoidance [2,9].¹

Therefore, in this paper we modify the basic greedy interference avoidance procedure to (a) maximally reduce TSC at each iteration and (b) to include an aggressive component whereby users who reside in a more crowded portion of the signal space deliberately interfere with (attack) other users in more sparsely populated dimensions. The procedure, dubbed class warfare, allows escape from suboptimal minima, and coupled to the finite number of possible fixed point TSC values for greedy interference avoidance, forces convergence to codeword sets which minimize the average mutual interference between codewords.

Along the way it will also be shown directly via elementary linear algebra and a variant of stochastic ordering methods that TSC minimization is equivalent to sum capacity maximization, and thereby, that greedy interference avoidance with class warfare achieves signal sets which meet sum capacity bounds. We note that a slightly more compact statement of this equivalence can be obtained by an appeal to matrix majorization theory [11,8,12]. However, the direct approach presented here is useful in that it can be wholly understood from first principles without collateral references.

2  Greedy Interference Avoidance: a brief review

We assume that user signals can be represented by N ×1 vectors s_m in some arbitrary signal space. The power of each signal vector is defined as p_m = |s_m|². Information is carried by corresponding independent zero mean, unit mean square b_m and the superposition bathed in some noise process, represented by a N ×1 noise vector w. The result is that the N ×1 received signal vector y is given by

y= Sb+ w

(1)

where b is the M ×1 vector of modulations corresponding to each codeword and S has M columns composed of the s_m. As a concrete example, the s_m might be the ±1 chip sequences of standard CDMA codewords. However, more generally, they could also be coefficient sequences for any convenient orthonormal signal representation.

The total interference power experienced by user m assuming a simple matched filter receiver is

E é ë æ è  smT |sm| [ Sb- sm bm + w] ö ø 2   ù û =  smT(SST+ W- sm smT) sm |sm|2

(2)

where

SST = M å m=1  sm smT

(3)

and W is the covariance matrix of the noise vector w.

Equation (2) suggests that user m could minimize the interference seen at the receiver by choosing s_m proportional to the eigenvector associated with the minimum eigenvalue of SS^T+W- s_m s_m^T. This simple intuitively pleasing greedy procedure when applied sequentially by all users, results at each iteration in the reduction of a quantity called the total square correlation (TSC) - a measure of the average interference seen by all users [1,2,3,4,5]:

TSC = Trace[ (SST+ W)2 ]

(4)

Furthermore, empirically speaking, the fixed point reached by this iterative procedure invariably has the absolute minimum TSC attainable [5]. Other procedures have also been shown to reduce TSC [1,3], but here we consider only greedy procedures which reduce interference for each user if at all possible. A formal statement of the greedy algorithm used here is provided in Appendix A.

At any fixed point of the algorithm, each s_m must obviously be an eigenvector of SS^T+ W. Equally obvious, the s_m associated with different eigenvalues must be orthogonal ([13], pp. 212). This orthogonality leads to the observation that if l_I is the eigenvalue for s_k and l_II the eigenvalue for s_l, k ¹ l, then we must also have l_I - p_k £ l_II since otherwise user k could reduce its interference by setting s_k=Ö{p_k}s_l/|s_l|.

3  Convergence Via Class Warfare

It is easily seen that there may exist many such fixed points with differing TSC values. Thus, if we seek to show that greedy interference avoidance can absolutely minimize TSC, we must first provide some means of escape from local minima. Then, since interference avoidance monotonically reduces TSC toward fixed points, if we show that the possible number of fixed point TSC values is finite, eventual convergence to the absolute minimum TSC is unavoidable. To these ends we provide formal escape methods in which users ``attack'' other users or signal dimensions by deliberate interference, or artful encroachment on less crowded portions of the signal space.

It should be noted that since we assume all user signals are collected at common antennas and it is the reception point which feeds optimal codewords back to users, the notion of unilateral ``attack'' is more a useful analogy than an operational principle. That is, class warfare is more an analytic method to escape suboptimal minima than a distributed algorithmic method of guaranteeing minimum TSC ``in the wild''. Of course, as software radios become more powerful and sophisticated, a useful systems-level paradigm might have semi-autonomous software agents responsible for decoding each user's signal as opposed to the centralized multiuser architectures of today [14,15,16,17,18,19]. In such a case, where agents may or may not collaborate directly, a warfare analogy might be more accurate. However, since all previous numerical experiments indicate that interference avoidance algorithms seem to converge without the help of escape methods or which codeword is chosen for replacement at a given step, even here the point is somewhat moot, and we reiterate that the term class warfare is a conceptual crutch for an analytic method of TSC minimization.

3.1  Some Preliminaries

Assume with no loss of generality that the equilibrium codeword ensemble consists of three known sets {a_k,b_l,c_j } such that

SST = Ka å k=1  ak akT+ Kb å l = 1  bl blT+ M-Ka-Kb å j=1  cj cjT

(5)

and (W+ SS^T) a_k = l_Ia_k, (W+ SS^T) b_l = l_IIb_l and (W+ SS^T) c_j = l_jc_j with l_I > l_II and l_j ¹ l_I,l_II. By virtue of their different eigenvalues, codewords of different classes, {a_k,b_l,c_j }, are mutually orthogonal. Finally, since it is possible that the codewords might not span Â^N, we also admit the possibility of a set { d_m } of eigenvectors for (W+SS^T) with cardinality K_d and associated eigenvalues l_m which are themselves mutually orthogonal as well as orthogonal to the codeword sets {a_k,b_l,c_j }.

For equal power codewords, each codeword from the set {a_k} suffers greater interference than each codeword from the set {b_l}. For unequal power, we can only say that set {a_k} is in a more energetic (including the set energy) portion of the signal space than set {b_l}. The assumption that the codeword constellation be a fixed point of a greedy interference avoidance algorithm requires l_I - l_i £ min_k|a_k|² where l_i is any other eigenvalue of W+SS^T.

We assume a basis set {f_i }, i=1,2,¼,n₁, which spans {a_k} and is orthogonal to {b_l} and {c_j}. Likewise we assume a basis set { y_j}, j=1,2,¼,n₂, (n₁+n₂ £ N) which spans {b_l} and is orthogonal to {a_k} and {c_j}, and a basis set { q_m }, m=1,2,¼,N-n₁-n₂ which spans both the {c_j} and {d_m} and is therefore orthogonal to {a_k} and {b_l}. We will later show (Theorem 2) that we can always choose these eigenvector sets as appropriate partitions of the eigenvector set of W. But for this case where we assume all codewords are known, we leave {f_i }, {y_j } and {q_m } as convenient bases for their respective codeword sets. As a specific example, since all the elements of {a_k} have the same eigenvalue, l_I (and similarly for {b_l}), we can assign with no loss of generality, f₁ = a₁/|a₁| and y₁=b₁/|b₁|.

3.2  Warfare Algorithm Overview

An ``attack'' is the placement of energy from (aggrieved) users residing in a more crowded portion of the signal space into a dimension occupied by (offending) users in a more sparsely populated portion of the signal space. Such an attack adds interference to the offending users and will elicit an avoidance response which overall reduces TSC. The specific method of attack is a simple rotation of the aggrieved codeword (or set of codewords) toward the offending user codeword (or dimension).

We will analyze three different attack methods. The first is an attack by one user directly on another. The second is an attack by a group of users in the same class on a dimension in the offending class. In both these cases, TSC reduction is dependent upon a reaction (codeword movement) by the attacked users and will be effective only if certain requirements are met. The final method of warfare is used when the first two are ineffective, and is actually more of a ``migration'' than an attack since it does not depend on the reaction of the attacked dimension but only on the coordination of the attack by aggrieved users. If no warfare method will reduce TSC, then it will be shown that TSC is minimized.

Loosely stated, the warfare-augmented greedy interference avoidance algorithm is:

1. Apply greedy interference avoidance until convergence to a fixed point codeword ensemble.
2. If warfare can reduce TSC, apply it and then go to 1).
3. If warfare cannot reduce TSC, the ensemble has attained minimum TSC.

3.3  Attacking the Devil You Know

Consider a scenario with a single aggrieved user a₁ having eigenvalue l_I and a known user b₁ with eigenvalue l_II < l_I. We must have l_I - l_j £ |a₁|² = p₁ where l_j is any eigenvalue of W+ SS^T and therefore l_I - l_II £ p₁ since otherwise, simple greedy interference avoidance could be used to reduce TSC. We assume that p₁ = 1 with no loss of generality² so that f₁ = a₁. Likewise we assume b₁ = by₁ where |b₁|² = b². The aggrieved user a₁ ``attacks'' user b₁ by adjusting its codeword to

a1¢ = (cosw) f1 + (sinw) y1

(6)

so that

a1¢ (a1¢)T = (cos2 w) f1f1T + (sin2 w)y1 y1T+  1 2 (sin2w)(y1f1T+f1y1T)

(7)

for some non-zero w.

User b₁ will react to this challenge by replacing b₁ with b₁¢, the new minimum eigenvalue eigenvector. That is,

(W+ SST- a1 a1T + a1¢(a1¢)T - b1 b1T)b1¢ = l* b1¢

(8)

where l^* is the minimum eigenvalue of

G = W+ SST- a1 a1T + a1¢(a1¢)T - b1 b1T

(9)

We then note that

Gfi = lIfi

(10)

for i=2,3,¼, n₁

Gyj = lIIyj

(11)

for j=2,3,¼, n₂, and

Gqm = lmqm

(12)

for m=1,2,¼, N-n₁-n₂. We therefore have N-2 eigenvectors for G. Since f₁ and y₁ are orthogonal to these, the remaining two (new) eigenvectors must be linear superpositions of f₁ and y₁, x = x₁ f₁ + x₂ y₁. Depending upon w, the best new codeword b₁¢ might be one of these two new eigenvectors, or could be another one entirely chosen from equations (10), (11) and (12). However, we will restrict our attention to b₁¢ of the form

b1¢ = b[ (sinc) f1 + (cosc) y1 ]

(13)

and note that a potentially better choice might exist. That is, by showing suitable selection of c in equation (13) can strictly reduce TSC, we will have also shown that a better response to attack can only decrease TSC even more.

With b₁¢ as in equation (13) we then have

b1¢ (b1¢)T = b2 é ë (sin2 c) f1f1T + (cos2 c)y1 y1T+  1 2 (sin2c)(y1f1T+f1y1T) ù û

(14)

Now we calculate the difference in TSC after the attack and response,

D = Trace[ (SST+ W)2 ] - Trace[ (G+ b1¢ (b1¢)T)2 ]

(15)

Making the required substitutions and defining

Q(w,c) = - [sin2 w- b2sin2 c]f1f1T + [sin2 w- b2 sin2 c] y1 y1T +  1 2 [(sin2w) + b2 (sin2c)] (y1f1T+f1y1T)

(16)

we obtain

D(w,c) = -2 Trace[ (SST+ W)Q(w,c) ]- Trace[ Q(w,c)Q(w,c) ]

(17)

Performing the indicated substitution and remembering that (SS^T+ W) f = l_I f and (SS^T+ W) y = l_II y yields

1 2 D(w,c) = d(sin2w- b2 sin2 c) - [sin2 w- b2sin2 c]2 -  1 4 [sin(2w) + b2 sin(2c)]2

(18)

where d = l_I - l_II. We note that 0 < d £ 1 since we assumed p₁ = |a₁|² = 1.

We need to determine whether D > 0 for some choices of w. However, we first note that for any given w, the response b₁¢(c) to the attack by a₁¢(w) will maximize D [5]. Therefore, we first seek the maximizing c for equation (18). Algebraic manipulations and trigonometric identities applied to equation (18) yield,³

1 2 D(w,c) = (d-(1-b2))sin2w-  1 2 b2(d+b2) +  1 2 b2 [(d- (1-b2)) (cos2c) + cos(2c+2w) ]

(19)

We then note that

max x  |A cos2x + B cos(2x+2w)| = Ö   (A + Bcos2w)2 + B2 sin2 2w

(20)

Therefore letting G = d+b² we have for A = G-1 and B=1,

max c   1 2 D(w,c) = (G-1) sin2 w -  1 2 (G-d) G é ê ë 1 -   æ Ö 1 - 4  G-1 G2 sin2 w   ù ú û

(21)

We then note that D(w,c) > 0 relies on having G- 1 > 0 which in turn implies G- d > 0 since d £ 1. Thus, the positivity of equation (21) rests on whether $w such that

(G-1) sin2 w >  1 2 (G-d) G é ê ë 1 -   æ Ö 1 - 4  G-1 G2 sin2 w   ù ú û

(22)

and we note that the term inside the radical is non-negative so that the right hand side of equation (22) is non-negative. Rearranging we have

1 - 2  G- 1 G- d  1 G sin2 w <   æ Ö 1 - 4  G-1 G2 sin2 w

(23)

and we again note that since the term inside the radical is non-negative (4(G-1)sin²w/G² £ 1 ) that the left hand side of equation (23) is non-negative as well. So, squaring both sides and simplifying leads to

G- 1 G- d sin2 w < d

(24)

which is true for some small enough w, so long as d > 0.

Thus,

d > 0

(25)

and

G- 1 = d- (1-b2) > 0

(26)

suffice for the existence of an w such that D(w,c) > 0. We summarize and generalize the result as a theorem:

Theorem 1 Suppose a single user with codeword power a² and eigenvalue l_I attacks another user with codeword power b² and eigenvalue l_II < l_I by adjusting its codeword according to equation (6). Further suppose that the attacked user responds by adjusting its codeword to obtain the maximum possible SINR. Then there exists an attack parameter w that will be successful in strictly reducing TSC if d = l_I - l_II > 0 and d > a² - b².

This result is intuitively pleasing since it makes little sense to engage in warfare if at best what you gain (l_II-b²) is no better than what you already have (l_I - a²). Reworking these two expressions leads directly to b² > a²-d. Another looser but more memorable condition can be had by noting that since d > 0, any b² ³ a² allows D(w,c) > 0. Since b² = a² implies equal power aggrieved and offending users, b² > a² implies a weaker user attacking a stronger user. Thus, we may say that TSC can always be strictly reduced whenever a less powerful user with associated eigenvalue l_I attacks an equal or more powerful user with associated eigenvalue l_II < l_I.

3.4  Attacking the Devil You Don't Know

We will find the following two theorems useful. The first theorem pertains to the relationship between equilibrium codeword sets and the eigenspace of the noise covariance matrix W.

Theorem 2 At equilibrium, codewords with different eigenvalues reside in mutually orthogonal spaces. These spaces are spanned by mutually orthogonal partitions of an eigenvector set for W. Furthermore, W shares a complete set of eigenvectors with SS^T+W at equilibrium.

Proof: Theorem 2  Consider a set of codewords { a_i } with cardinality m₁, dimensionality n₁ and associated unique eigenvalue l_a. Let us then define

SST= AAT + ZZT

(27)

where

AAT = m1 å i=1  ai aiT

(28)

and Z is a matrix containing the codewords with eigenvalues other than l_a. We then have

(SST+ W) ai = (AAT + ZZT + W) ai = (AAT + W)ai = la ai

(29)

Note that any linear combination of the { a_i } is also an eigenvector of SS^T+ W since all the a_i share the same eigenvalue l_a.

Since AA^T + W has a full set of eigenvectors and the { a_i } are spanned by exactly n₁ of them, there must be an additional N-n₁ eigenvectors f_m which lie in the orthogonal complement of {a_i } and therefore satisfy

(AAT + W) fm = Wfm = lm fm

(30)

so that they are eigenvectors of W as well. Since there are exactly N-n₁ of these eigenvectors, the remaining n₁ eigenvectors f_i, i=1,2,¼, n₁ of W must form the basis for the set {a_i}.

Extending this result, we see that for all sets of codewords with the same eigenvalue, there must be an associated set of eigenvectors of W which exactly spans the space of these codewords. Therefore, equilibrium codewords which share different eigenvalues reside in different partitions of the noise covariance signal space.

Finally, as mentioned previously, each of the eigenvectors of W which span the codeword space can be expressed as a suitable linear combination of codewords

m1 å i=1  mij ai = fj

(31)

j=1,2,¼,n₁. Therefore, since (SS^T+ W)s_m = l_a s_m we can also find (SS^T+ W)f_j = l_af_j with all the f_j eigenvectors of SS^T+ W with eigenvalue l_a. This completes the proof.  ·

It is worth mentioning that from this point onward we will express codewords as linear superpositions of the noise covariance eigenvector partition in which they reside as opposed to the arbitrary basis set used in section 3.3. The next theorem establishes a relationship between the mutual correlations of codewords in a given class and their projections onto a noise covariance eigenvector contained in that class.

Theorem 3 Let f_i, i=1,2,¼,N be a common complete set of eigenvectors for W and SS^T+ W (Theorem 2) with Wf_i = s_i f_i. Assume { f_i }, i=1,2,¼,L exactly spans the set of codewords s_k, k=1,2,¼,K which share the same eigenvalue l, (SS^T+W)s_k = ls_k.

If we define a_kl = s_k^T f_l, then for r_ij = s_i^T s_j we must have

K å j=1  ail ajl(rij - ail ajl) = 0

(32)

Proof: Theorem 3  By Theorem 2 and Mercer's theorem [20] we have

SST+ W = l L å i=1  fi fiT+ N å i=L+1  li fi fiT

(33)

where the { f_i } is the complete eigenvector set for W. Since the { s_k }, k=1,2,¼,K are exactly spanned by the f_i, i=1,2,¼,L we then have

l L å i=1  fi fiT = K å k=1  sk skT+ L å i=1  si fi fiT

(34)

which implies

K å k=1  sk skT = L å i=1  (l- si) fi fiT

(35)

We define E_i = l- s_i, the codeword energy along eigenvector f_i and note that for a_ki = f_i^T s_k we have E_i = å_k=1^K a_ki².

We then have

K å j=1  ail ajl (rij - ail ajl) = K å j=1  ail rijajl -ail2 El

(36)

and note that

K å j=1  ail rijajl = K å j=1  flT(si siT)(sj sjT)fl = flT(si siT) æ è L å i=1  Ei fi fiT ö ø flT = ail2El

(37)

which completes the proof.  ·

Now, let A be the aggrieved set of codewords with elements a_i such that (SS^T+ W)a_i = l_I a_i. We can write

ai = ai f1 + xi

(38)

where f₁ is one of the eigenvectors of W which spans the aggrieved codeword set. We note that (SS^T+ W) f₁ = l_If₁, that Wf₁ = s₁f₁ and that (SS^T+ W) x_i = l_I x_i.

Let S be the (non-empty) set of offending codewords with eigenvalue l_II < l_I. And by Theorem 2 let the noise covariance dimension f_N be contained in the span of S with (SS^T+ W)f_N = l_II f_N. For the codewords { s_i }, i Î S in this set we write

si = bi fN + ui

(39)

with b_i = f_N^T s_i. As for a we note that (SS^T+ W)f_N = l_IIf_N, that Wf_N = s_Nf_N and that (SS^T+ W) u_i = l_II u_i.

To attack, we rotate each a_i into f_N as

ai¢ = ai (coswf1 + sinwfN) + xi

(40)

and then script the evasion response by the offending set as

si¢ = bi (coscfN + sincf1) + ui

(41)

To calculate the change in TSC we write

ai¢(ai¢)T = aiaiT+ai2 [sin2wfN fNT-sin2wf1 f1T+coswsinw(f1 fNT + fN f1T) ] + ai(cosw- 1)(f1 xiT + xif1T)+aisinw(fN xiT + xifNT)

(42)

and

si¢(si¢)T = si siT+bi2 [sin2cf1 f1T-sin2cfN fNT+coscsinc(f1 fNT + fN f1T) ] + bi(cosc-1)(fN uiT + uifNT) +bi sinc(f1 uiT + uif1T)

(43)

Therefore,

S¢( S¢)T = SST+ å i Î A  ai2 [sin2wfN fNT-sin2wf1 f1T+coswsinw(f1 fNT + fN f1T) ] + å i Î A  ai(cosw- 1)(f1 xiT + xif1T)+ å i Î A  aisinw(fN xiT + xifNT) + å i Î S  bi2 [sin2cf1 f1T-sin2cfN fNT+coscsinc(f1 fNT + fN f1T) ] + å i Î S  bi(cosc-1)(fN uiT + uifNT) + å i Î S  bi sinc(f1 uiT + uif1T)

(44)

We then define the total aggrieved codeword energy in f₁ as a² = å_{i Î A} a_i², the total offending codeword energy in dimension f_N as b² = å_{i Î S} b_i² and form Q(w,c) as in section 3.3;

Q(w, c) = (a2 sin2w- b2 sin2c)(fN fNT-f1 f1T) + (a2 coswsinw+b2 coscsinc)(f1 fNT + fN f1T) + å i Î A  ai(cosw- 1)(f1 xiT + xif1T)+ å i Î A  aisinw(fN xiT + xifNT) + å i Î S  bi(cosc-1)(fN uiT + uifNT) + å i Î S  bi sinc(f1 uiT + uif1T)

(45)

We then define D(w,c) as in equation (17) and reduce it to

1 2 D(w,c) = d(a2 sin2 w- b2 sin2 c)-(a2sin2 w- b2 sin2 c)2-  1 4 (b2 sin2c+ a2 sin2w)2 - ((cosw-1)2 + sin2w) å i,j Î A  aiaj (kij - aiaj) - ((cosc-1)2 + sin2c) å i,j Î S  bibj (rij - bibj)

(46)

where k_ij = a_i^T a_j, i,j Î A, r_ij = s_i^T s_j, i,j Î S and d = l_I-l_II as before.

By Theorem 3 the terms in (cosw-1)² + sin²w and (cosc-1)² + sin²c must be identically zero so we have

1 2 D(w,c) = d(a2 sin2 w- b2 sin2 c)-(a2sin2 w- b2 sin2 c)2-  1 4 (b2 sin2c+ a2 sin2w)2 = a4 é ë  d a2 (sin2 w-  b2 a2 sin2 c)-(sin2 w-  b2 a2 sin2 c)2-  1 4 (sin2w+  b2 a2 sin2c)2 ù û

(47)

Equation (47) is identical to equation (18) within a factor of a⁴ if we define [(d)\tilde] = d/a² and [(b)\tilde] = b/a². Therefore the result is identical to that in section 3.3: TSC will be strictly reduced by dimensional attack so long as [(d)\tilde] > 0 and [(d)\tilde] > 1 - [(b)\tilde]² which reduces to d > 0 and d > a² - b². The only difference is that we have launched a coordinated attack and have ``scripted'' an ensemble response (specifically, a rotation by all offending users from the attacked dimension f_N toward the attacking signal dimension f₁) as opposed to assuming individual greedy responses by each codeword.

3.5  Leveling the Playing Field Through Cooperation

As with dimensional attack assume there exist codewords { s_i }, i=1,2,¼,K such that (SS^T+ W) s_i = l_I s_i and we assume the codewords occupy n < N dimensions. Each codeword ``attacks'' y by forming

si¢ = coswi si + sinwi Ö   pi   y

(48)

so that

si¢(si¢)T = sisiT - sin2 wi si siT+ pisin2 wi yyT +  1 2 Ö   pi   sin2wi(si yT + ysiT)

(49)

Now we form the new S¢(S¢)^T + W as

S¢(S¢)T + W = SST+ W+ Q

(50)

where Q = å_i=1^K [s_i^¢(s_i^¢)^T - s_i s_i^T]. Using equation (49) we have

Q = - K å i=1  sin2 wi (si siT - piyyT) + K å i=1   1 2 Ö   pi   sin2wi (si yT + ysiT)

(51)

As found previously (see equation (17)), the difference in TSC before and after migration is D = -2Trace[ (SS^T+ W)Q] - Trace[ Q² ]. So defining d = l_I - l_II as before and r_ij = s_i^T s_j we have

1 2 D(W) = d K å i=1  pi sin2 wi- K å i,j=1  sin2wisin2wj(rij2 + pi pj)-  1 4 K å i,j=1  Ö   pi   Ö   pj   rijsin2wisin2wj

(52)

Now, for small enough w_i, terms on the order of sin⁴(·) become insignificant and we have

1 2 D(W) » d K å i=1  pi wi2- K å i,j=1  Ö   pi   wirij Ö   pj   wj

(53)

If we define

v = é ê ê ê ê ê ë v1 v2 : vK ù ú ú ú ú ú û

(54)

where v_i = Ö{p_i} w_i we see that

1 2 D(W) » d K å i=1  pi wi2-vT Zv

(55)

where Z is a matrix whose entries are z_ij = r_ij.

We then note that the K ×K matrix

Z = é ê ê ê ê ê ê ê ë - s1 - - s2 - - :- - sK - ù ú ú ú ú ú ú ú û é ê ê ê ê ê ë | | | | s1 s2 ¼ sK | | | | ù ú ú ú ú ú û

(56)

will be singular if the s_i are linear combinations of only n < K eigenvectors f_j. In such a case there exists a non-zero vector v for which v^T Zv = 0. And since då_i=1^K p_i w_i² > 0 for any of the w_i nonzero, we can always find a set of suitably small {w_i } for which D(W) > 0.

We summarize the result as a theorem:

Theorem 4 Let {s_i} be the set of all codewords which share a common eigenvalue l_I. Let y be an eigenvector of W orthogonal to all the { s_i } and for which (SS^T+ W)y = l_II y where l_I - l_II = d > 0. TSC can always be strictly reduced by coordinated attack on dimension y if the number of codewords is at least one more than the number of dimensions they span.

4  Properties of Eigenvalue Sets for SS^T+ W

Since TSC is the trace of (SS^T+ W)² we see that TSC depends only on the eigenvalues of SS^T+W, { l_i }. That is, Trace[ (SS^T+W)² ] = å_i l_i². To more easily distinguish one eigenvalue set from another, we assume that each set is ordered from largest to smallest and define such ordered sets as l-constellations. We will then derive order bounds which must be obeyed by all possible l-constellations and show that when the bounds are met with equality, TSC is minimized and that almost incidentally, the sum capacity (see Appendix C) of the codeword set is maximized.

4.1  Bounds On Partial Sums of Ordered Eigenvalues

Now, for any matrix Q with eigenvalues { m_i } ordered from largest to smallest we have ([13], pp. 253),

max xiT xj = dij  k å i=1  xiT Qxi = k å i=1  mi

(57)

Consider then

SST+ W= M å i=1  si siT+ N å j=1  sj fj fjT

(58)

and that

max |x|=1  xT (SST+ W) x = l1

(59)

It follows immediately that l₁ ³ s₁ and l₁ ³ |s₁|² + s_N = p₁ + s_N. Equally obvious is that l₁ ³ (P+U)/N [5,6,8]. Slightly less obvious is that

l1 ³  1 k k å i=1  (pi + sN-i+1)

(60)

for k=1,2,¼, N-1. This may be shown by noting that å_i=1^k l_i ³ å_i=1^k (p_i + s_N-i+1) and that the minimum maximum l₁ must then be at least this quantity divided by k.

Therefore, we must have in total

l1 ³ max é ë s1, max 0 < k < N   1 k k å i=1  (pi + sN-i+1),  P+U N ù û

(61)

and we will show that equation (61) may be used recursively to bound the quantity å_i=1ⁿ l_i. In what follows we denote the eigenvector of (SS^T+ W) associated with l_i as y_i.

Since we seek the smallest possible l₁ we must consider in turn each possibility expressed in equation (61). So to start, suppose s₁ is the minmax l₁ bound. To meet the bound, no codeword can have energy along f₁ since otherwise we must have l₁ > s₁. So, if y₁ = ax+ Ö{1-a²} f₁ where x^f₁ is the eigenvector with largest eigenvalue s₁, then we must also have

(SST+ W) x= s1 x

(62)

which implies that $u^y₁ also with eigenvalue s₁. The overall implication is that we must have l₂ ³ s₁ as well.

Now consider that with y₁=f₁ we have

l2 ³ max é ë s2, max 0 < k < N-1   1 k k å i=1  (pi + sN-i+1),  P+U - s1 N-1 ù û

(63)

and we note that since we have

max é ë s1, max 0 < k < N   1 k k å i=1  (pi + sN-i+1),  P+U N ù û = s1

(64)

we must also have

max é ë s2, max 0 < k < N-1   1 k k å i=1  (pi + sN-i+1),  P+U- s1 N-1 ù û £ s1

(65)

a bound smaller than that if y₁ ¹ f₁. Thus, equation (63) is the lowest lower bound on the minmax l₂ for l₁ = s₁ and can also be seen as a recursive application of equation (61) after f₁ has been expurgated from the ensemble and the dimensionality of the problem decreased by 1.

Continuing sequentially with the terms in equation (61), now suppose that instead of s₁, we have p₁+s_N as the minmax l₁ bound. To meet this bound we must have y₁ = f_l and s₁ = Ö{p₁}f_l for any l such that s_l = s_N. If not then l₁ must be strictly greater than p₁+s_N. We then have

l2 ³ max é ë s1, max 1 < k < N   1 k-1 k å i=2  (pi + sN-i+1),  P+U- p1 - sN N-1 ù û

(66)

As before, we note that equation (66) is a recursive application of equation (61) with s₁ and f_N expurgated.

Finally we consider the last term in equation (61) and suppose that now [(p₁ + p₂ + s_N + s_N-1)/2] is the minmax l₁ bound. Since we must have l₁ +l₂ ³ p₁ + p₂ + s_N + s_N-1, if the minmax bound for l₁ is met with equality, we must have l₂ = l₁ and we are left to bound l₃ as

l3 ³ max é ë s1, max 2 < k < N   1 k-2 k å i=3  (pi + sN-i+1),  P+U - p1 - p2 - sN - sN-1 N-2 ù û

(67)

which is an application of equation (61) with codewords s₁ and s₂ and dimensions f_N and f_N-1 expurgated.

In general, if

max é ë s1, max 0 < k < N   1 k k å i=1  (pi + sN-i+1),  P+U N ù û =  1 n n å i=1  (pi + sN-i+1)

(68)

and n < N we will have

l å j=1  lj ³  l n n å i=1  (pi + sN-i+1)

(69)

for l £ n and

ln+1 ³ max é ê ë s1, max n < k < N   1 k-n k å i=n+1  (pi + sN-i+1), P+U - n å i=1  (pi + sN-i+1) N-n ù ú û

(70)

And once again we note that equation (70) is simply equation (61) applied after s₁,s₂,¼, s_n and f_N,f_N-1,¼, f_N-n+1 have been expurgated. Therefore, we see that equation (61) can be used as a recursive kernel to generate the least lower bound for partial sums of ordered eigenvalues l_i.

As a specific example consider, s = (26,6,4,4) and p = (4, 3, 2, 1). Application of equation (61) has l₁ ³ s₁ = 26. Expurgation of the associated dimension leaves us with s¢ = (6,4,4) and l₁ + l₂ ³ 34 = 26 + p₁ + s₃¢. After expurgating p₁ and s₃¢ we are left with s^¢¢ = (6,4) and p^¢¢ = (3, 2, 1). Applying the bound again we have l₃ + l₂ + l₁ ³ 42 = 34 + (p₁ + p₃^¢¢ +p₃^¢¢ + s₁^¢¢ + s₂^¢¢)/2. As another example⁵, consider s = (1.1,1,0) and p = (1, 1, 1/5). In this case l₁ ³ 3/2 and l₁ + l₂ ³ 3.

In general, is it clear that when the bound for å_i=1ⁿ l_i is plotted against n, the result must be a concave segmented arc above the line n(P+U)/N as illustrated in FIGURE 1 for the first example.

4.2  The Lower Bound Is the Optimal l-Constellation

The definition of the constraint set in the previous section specifies ordered eigenvalues and partial sums of eigenvalues. To this end let us define

FX(k) = k å j=1  xj

(71)

k=1,2,¼,N and where the x_j ³ 0 are ordered x_j ³ x_j+1. The reader will note that F_X(k)/F_X(N) is exactly the cumulative distribution function of an ordered probability distribution x_j/F_X(N), i=1,2,¼,N - a variation on stochastic ordering [21,22,23]. To avoid confusion we note that the term ``stochastic'' is irrelevant in our context since we do not consider random variables, but make mention of it because the mathematics of ordered distributions is useful for our purposes. ⁶ The necessary result is now stated as a theorem.

Theorem 5 Suppose two non-negative non-increasing sequences {x_j} and {r_j} have F_X(k) ³ F_R(k) k=1,2,¼,N-1 and F_X(N) = F_R(N) = 1. For any convex function g() we must have G(x) = å_j=1^N g(x_j) ³ å_j=1^N g(r_j) = G(r). If g() is concave, then G(x) £ G(r).

A proof of this (known) result is provided in Appendix D for convenience.

We then note that for any two ordered eigenvalue sets { l_j⁽¹⁾ } and { l_j⁽²⁾ } with å_j=1^N l_j⁽ⁱ⁾ = (P+U) and å_j=1^N l_j⁽¹⁾ ³ å_j=1^N l_j⁽²⁾, we may normalize by P+U to obtain x and r respectively as defined in Theorem 5. We further note that

TSC(x) = (P+U)2 N å j=1  xj2

(72)

and (see Appendix C)

Cs(x) =  1 2 N å i=1  logxi +  1 2 N å i=1  log(P+U)-  1 2 N å i=1  logsi

(73)

Since g(x_j) = x_j² is convex, TSC(x) ³ TSC(r). Likewise since g(x_j) = logx_j is concave we have C_s(x) £ C_s(r).

Therefore, since the bounds generated by recursive application of equation (61) describe the ordered set of possible eigenvalues with smallest ``stochastic'' order, TSC is minimized and C_s is maximized by eigenvalue sets which attain the bound. For emphasis, we state this result as a theorem.

Theorem 6 For a set of codewords { s_i } with ordered powers p_i ³ p_i+1, i=1,2,¼,M in a space of dimension N with noise covariance W, sum capacity is maximized and TSC minimized when the partial sums of non-increasingly ordered eigenvalues, {l_i}, of SS^T+ W attain the lower bounds generated by recursive application of equation (61).

The eigenvalue structure of such sets is illustrated in FIGURE 2 We prove their existence in the next section.

5  Warfare Minimizes TSC (Maximizes Sum Capacity)

Through a progression of theorems we examine fixed points for warfare-augmented greedy interference avoidance and show equivalence between the implied eigenvalues of SS^T+ W and the eigenvalues given by the lower bounds derived from equation (61). We start with some preliminary theorems which will be used extensively throughout. We follow these with theorems which parallel the three terms in equation (61) and then a theorem which states that the only true equilibrium for greedy interference avoidance with class warfare is an optimum codeword ensemble. We close the section by showing that warfare-augmented greedy interference avoidance eventually achieves an optimum ensemble after traversing at most a finite number of suboptimal minima.

5.1  Preliminaries

We would like to drive this distribution toward the optimal distribution given in FIGURE 2. To this end, consider the following set of assertions which establish the codeword occupancy of the various noise covariance dimensions.

As a corollary of Theorem 1 we have

Corollary 1 Suppose single user warfare cannot reduce TSC for a given codeword set { s_i } with associated eigenvalue l_I. Then, the codeword energies p_i = |s_i|² for all elements of this set must at least as large as that for all other codewords outside the set with eigenvalues l_II < l_I.

Theorem 7 Let {s_k } be the set of all codewords with eigenvalue l_I. Suppose there exists a signal dimension y, an eigenvector of W with (SS^T+W) y = l_IIy, Wy = gy and l_II < l_I but TSC cannot be reduced by dimensional attack. Then the partition of noise covariance eigenvectors f_i which spans {s_k } must all have eigenvalues { s_i } no larger than g, the noise covariance eigenvalue associated with y.

Proof: Theorem 7  Let E_f be the signal energy along dimension f. We then have l_I = E_f + s_f. Likewise define the signal energy E_y as the signal energy along y so that l_II = E_y+g. For dimensional attack to be ineffective, we must have d £ E_f - E_y which implies E_f+s_f - (E_y+g) £ E_f - E_y which in turn implies s_f - g £ 0 for any f in the spanning set of { s_k } thus proving the theorem.  ·

The following theorem is implied directly by Corollary 1 and Theorem 7 and is stated without proof.

Theorem 8 Let s_i and s_j be codewords with eigenvalues l_I and l_II respectively. Let each reside in spaces which contain largest noise covariances g_i and g_j respectively. If |s_i| ³ |s_j|, then l_I ³ l_II (Corollary 1) and g_i £ g_j (Theorem 7).

In words, at equilibrium a higher power codeword has an eigenvalue at least as large as that of a lower power codeword. In addition, a higher power codeword resides in a partition of the noise covariance space with variances at least as small the space in which a lower power codewords resides.

It is useful to note that Theorem 8 implies that higher power codewords command the best noise space partitions and that lower power codewords are relegated to higher power noise space partitions. Although this is not in keeping with the egalitarian spirit of class warfare, it is (unfortunately) in keeping with the physical reality that might often makes right!

5.2  The Bounds of Equation (61)

The next three theorems address the three terms inside the max function of equation (61) and will be used directly to show that the warfare procedure produces eigenvalue sets which meet the lower bound specified by recursive application of equation (61).

Theorem 9

Minmax [s₁ ]: If s₁ is the minmax eigenvalue bound in equation (61) then at equilibrium, all codewords must be orthogonal to f₁.

Proof: Theorem 9  Suppose at some equilibrium $s₁ with nonzero projection onto the eigenvector f₁ associated with s₁. This codeword must then have eigenvalue l_I > s₁. Now we note that since s₁ is the minmax eigenvalue bound we must also have by equation (61) that s₁ ³ (P+U)/N where P is the total codeword energy and U is the total noise energy. Since the eigenvalues of SS^T+ W must sum to P + U, if $l_I > s₁ ³ (P+U)/N then $l_II with l_II < s₁ < l_I which in turn implies that $f_i with (SS^T+ W)f_i = l_IIf_i and Wf_i = s_if_i with s_i < s₁ since l_II ³ s_i. This contradicts Theorem 7. Thus, no codeword energy can exist along dimension f₁ at equilibrium if s₁ is the minmax bound for l₁.  ·

Theorem 10

[Minmax [ 1/k] å_i=1^k (p_i + s_N-i+1) ]: Define

g =  1 k k å i=1  (pi + sN-i+1)

(74)

where k is the largest integer < N such that

1 k k å i=1  (pi + sN-i+1) ³  1 n n å i=1  (pi + sN-i+1)

(75)

n=1,2,¼,N-1.

If the bound of equation (61) is equal to g, then at an equilibrium where warfare cannot reduce TSC, the largest k codewords, s₁,s₂,¼,s_k, will reside in the space spanned by f_N,f_N-1,¼,f_N-k+1 with the smallest k noise covariances, s_N,s_N-1,¼,s_N-k+1. These codewords will share the same eigenvalue l_I = g and will therefore meet the lower bound for the first k eigenvalues specified by equation (61).

Proof: Theorem 10  Let S be the set of all codewords (cardinality L) with the largest eigenvalue l_I. Assume this set spans an n-dimensional space. By Theorem 8 these L codewords must be the largest L codewords s₁,s₂,¼,s_L and will span the lowest n noise dimensions.

Now if there exists a codeword s_L+1, it must have eigenvalue l_II < l_I by the definition of S as containing all codewords with eigenvalue l_I. Therefore we must have L=n since otherwise, group migration (Theorem 4) could be applied to reduce TSC. So we must have

lI =  1 n n å i=1  (pi + sN-i+1)

(76)

and the first n eigenvalues of SS^T+ W are l_I. However, by equation (61) we must also have l₁ ³ g which is a direct contradiction unless

1 n n å i=1  (pi + sN-i+1) = g

(77)

We then note that if equation (77) is true for some n < k then by the definition of g we must also have

1 k-n k å i=n+1  (pi + sN-i+1) = g

(78)

as well. But this is impossible since by construction we require the largest eigenvalue outside S to be l_n+1 < l_I = g and recursive application of equation (61) to the remaining codewords s_L,¼,s_M in noise dimensions f_N-n,f_N-n-1,¼,f₁ along with satisfaction of equation (78) requires that l_n+1 ³ g. Thus, n cannot be less than k.

Now suppose n > k. Then l₁ = l_I £ g and l₁ ³ g is a direct contradiction owing to the ``largest k'' stipulation in the definition of g. That is, there exists no n > k such that l_I ³ g. Thus, we must have n=k.

So in summary, if g as defined in equation (74) is the minmax bound on l₁, then at any equilibrium where warfare cannot be used to reduce TSC, the k highest power codewords must reside in the k lowest power noise dimensions and share the same eigenvalue g, unique and the largest over all codewords.  ·

Theorem 11

[ Minmax [(P+U)/N] ]: If the minmax bound for l₁ is (P+U)/N, then all codewords must share the same eigenvalue l_I = (P+U)/N at an equilibrium where warfare cannot reduce TSC.

Proof: Theorem 11  As in Theorem 10, let S be the set of L highest power codewords residing in the n lowest power noise dimensions. By Theorem 4, unless L=n, any difference in eigenvalues can be exploited to reduce TSC. Therefore, unless all the eigenvalues are already equal to (P+U)/N, we must have

lI =  1 n n å i=1  (pi + sN-i+1)

(79)

However, since (P+U)/N is the minmax value of l₁, the structure of equation (61) requires l_I ³ (P+U)/N, a condition which can only be met if l_I = (P+U)/N. By the assumed monotonicity of eigenvalues for SS^T+W, if l₁ = (P+U)/N, then all the eigenvalues must be (P+U)/N thus completing the proof.  ·

5.3  The l-Constellation Bound Is the Stopping Condition

Theorem 12 The only stable codeword ensembles for warfare-augmented greedy interference avoidance are those which meet with equality the eigenvalue bound generated by recursive application of equation (61).

Proof: Theorem 12  Suppose the conditions of Theorem 9 are satisfied. Then at equilibrium the bound on l₁ specified by equation (61) is met with equality since no codeword energy resides in f₁. All the codewords and remaining dimensions are orthogonal to f₁.

Alternately, suppose that the conditions of Theorem 10 are satisfied for some k < N. Then once again, the bound specified in equation (61) is met with equality and the remaining codewords s_k+1,s_k+2,¼,s_M must reside in noise dimensions f_N-k,f_N-k-1,¼, f₁, orthogonal to codewords s₁,s₂,¼,s_k which reside in dimensions f_N,f_N-1,¼, f_N-k+1. Similarly, if the conditions of Theorem 11 are satisfied, then the bound specified in equation (61) is met with equality and all the eigenvalues of SS^T+W are identical.

In each of these three cases, the codeword and dimension partitioning implied by the fixed point exactly parallels the partitioning implied by equation (61). Thus, equation (61), Theorem 9, Theorem 10 and Theorem 11 can be applied at each step to an independent smaller problem until no codewords or dimensions remain.

Since at each recursive step the bound of equation (61) is met with equality, stable equilibrium ensembles for warfare-assisted greedy interference avoidance are only those ensembles which minimize TSC and maximize sum capacity.  ·

So in summary, recursive expurgation of largest eigenvalue signal dimensions and codewords in the equilibrium set is identical to the codeword/dimension expurgation and recursive application of equation (61) used to establish the lower bound. Thus, the equilibrium set meets the bound at every step. Therefore, the equilibrium point for greedy interference avoidance, augmented by warfare techniques, is a codeword ensemble which maximizes sum capacity and minimizes TSC. Thus, a fixed point ensemble which is stable under class warfare in general has a codeword power distribution as depicted in FIGURE 2.

5.4  A Level Playing Field Attained, Eventually

So far, we have provided algorithms which strictly reduce TSC at fixed points not satisfying a set of stopping conditions, and we have shown that only optimum codeword ensembles can satisfy the stopping conditions. However, showing reduction can always be forced does not guarantee that an optimal value is achieved since there could be an infinite number of fixed point values which taken in some monotonic sequence might approach any number of values. Therefore, we now show that the number of possible greedy interference algorithm equilibrium TSC values is finite and that the warfare procedure must therefore eventually attain some unique TSC specified by the stopping conditions.

This possibly subtle assertion bears repetition. Although the number of possible algorithm fixed point ensembles is potentially infinite, we can show that the number of TSC fixed point values is finite. Since escape methods strictly reduce TSC at suboptimal equilibria, only a finite number of TSC values need be traversed and convergence to the optimal is assured.

For a set of codewords {a_i} which spans n₁ dimensions and shares the same eigenvalue l_a at equilibrium, by Theorem 2 the set must span some n₁-dimensional partition of the eigenspace of W. Let this partition be described by {y_i }, i=1,2,¼,n₁ where the y_i are eigenvectors of W (i.e., Wy_i = s_i y_i). If there are m₁ codewords in the set we must have

la =  1 n1 é ë m1 å i=1  |ai|2 + n1 å i=1  |Wyi|2 ù û

(80)

The maximum number of possible choices (without regard for feasibility) for assemblages of n₁ noise covariance eigenvectors and m₁ codewords is (N || (n₁))(M || (m₁)). Therefore, with the set ({n_i},{m_i}) denoting all possible (but again, potentially infeasible) partitions of M codewords into N dimensions, there are at most a (possibly large) but finite number of fixed point TSC values

Õ ({ni},{mi})  æ è N ni ö ø æ è M mi ö ø

(81)

This result along with those for warfare techniques and stopping rules admits the following summarizing theorem:

Theorem 13 Greedy interference avoidance coupled with class warfare allows escape from any fixed point which does not meet the stopping conditions for optimality. Since there are a finite number of fixed points, the composite algorithm is therefore guaranteed to attain the stopping points specified in section 5.3 and therefore achieve the minimum possible TSC and maximum sum capacity.

5.5  Practical Considerations: a quantitative sketch

However, in a practical setting, the greedy procedure would be stopped at some point and this would be close to, but perhaps not exactly a fixed point. Thus, for completeness, it is useful to consider the case where the codeword ensemble is ``almost'' at a fixed point and how warfare would be applied for such ensembles.

So, consider that greedy interference avoidance can be applied until codewords are within some small n of being eigenvectors of the signal plus noise covariance matrix (see Appendix A). More formally, for suitably large l and any codeword s_i(l) we have

|R(l) si(l) - li(l) si(l)|2 £ n2

(82)

Now suppose single user warfare is applied. We would have exactly equation (17)

D(w,c) = -2 Trace[ (SST+ W)Q(w,c) ]- Trace[ Q(w,c)Q(w,c) ]

(83)

but then instead of equation (18) we would have

1 2 D(w,c) = d(sin2w- b2 sin2 c) - [sin2 w- b2sin2 c]2 -  1 4 [sin(2w) + b2 sin(2c)]2 +O(n)

(84)

where the term in O(n) comes from the term -2 Trace[ (SS^T+ W)Q(w,c) ] and the imperfect eigenvectors which comprise the matrix Q. This basic form applies to the other types of warfare as well.

A ``practical'' warfare method would therefore apply greedy interference avoidance until an approach to a fixed point was detected via an initial n criterion, and then evaluate the potential decrease in TSC after warfare. If the potential decrease were much larger in magnitude than the O(n) term, then warfare would be applied. If not, then greedy interference would continue to decrease |n| until such time as warfare would be guaranteed effective. The algorithm would then stop when TSC was within some tolerance of optimal.

Thus, we close with the following more formal statement of warfare-assisted greedy interference avoidance:

1. Apply greedy interference avoidance until convergence to within some tolerance n of a fixed point codeword ensemble. If the fixed point is suboptimal, choose n so that |O(n)| is much less than the potential benefit from warfare.
2. If warfare can reduce TSC, apply it and then go to 1).
3. If warfare cannot reduce TSC, the ensemble has attained nearly minimum TSC, and greedy interference avoidance may be further applied to reduce TSC until satisfied.

6  Summary and Conclusion

It must be noted, however, that in all numerical experiments with both greedy interference avoidance [5,4,2] and MMSE interference avoidance [1,3], when starting from randomly chosen initial codewords, essentially optimal sets were obtained within approximately three cycles of codeword adaptation and never required intervention with warfare-like methods. That is, direct application of interference avoidance principles was enough to ensure empirical convergence. Why this convergence to optimal codeword ensembles is so robust for simple interference avoidance methods remains an open question. We note that implicit in each warfare method described is a number of (gradient-like) directions for escape from local minima. Perhaps careful characterization of the dimensionality of potential escape trajectories relative those trajectories which tend to trap an ensemble in a local minimum might prove useful. Specifically, if approach trajectories are of zero measure, then small stochastic perturbations would be effective in avoiding local minima as was used in recent work [10] by Pablo Anigstein at UCB.

A  The Greedy Interference Avoidance Algorithm

An informal statement of a greedy interference avoidance algorithm would be:

1. A minimum eigenvalue eigenvector, f of R_i = SS^T+ W- s_i s_i^T is determined.
2. s_i is replaced by f iff
   

   fT Ri f < siT Ri si

   (85)

   which strictly reduces TSC. Otherwise, s_i is unchanged.
3. The procedure is repeated sequentially for every user i.

However, TSC convergence does not necessarily imply codeword ensemble convergence. And since warfare methods presume the attainability of ensembles where every codeword is an eigenvector of the noise plus signal covariance matrix, provable convergence to such sets is a necessity. This is provided in the following theorem for a slightly modified version of greedy interference avoidance where at each iteration, the codeword chosen for replacement is that whose replacement will minimize TSC. We call this variant greedy+ interference avoidance.

Theorem 14 With iterative application of greedy+ interference avoidance, codewords must converge to ensembles where each codeword is an eigenvector of the signal plus noise covariance matrix R = R_i + s_i s_i^T.

Proof: Theorem 14  First we define an iteration l as a greedy interference avoidance step where a codeword s_il(l) is replaced. We assume that codeword s_il(l) is the codeword which when replaced will produce the greatest reduction in TSC. We then have

dil (l) = sil T (l)Ril(l)sil(l)-xil(l) T Ril(l)xil (l) ³ 0

(86)

as the difference between the TSC value at iteration l and l+1 where x_il (l) is the minimum eigenvalue eigenvector of R_il(l) [5]. We note that

dil(l) = max i  di (l)

(87)

and is therefore the maximum possible d_i(l) at iteration l.

Since greedy interference avoidance converges in TSC we have

lim l® ¥  dil(l) = 0

(88)

Now consider that the difference in TSC values before and after the potential replacement of any codeword s_i at iteration l can be written as

dil(l) ³ di(l) = siT (l)Ri(l)si(l)-xi(l) T Ri(l)xi (l) ³ 0

(89)

We define the eigenvalues of R_i(l) as { l_ij(l) }, j=1,2,¼, N and assume that they are ordered from largest to smallest. If we further define the corresponding eigevectors as f_ij(l), j=1,2,¼, N we can rewrite s_i(l) as

si(l) = N å j=1  aij(l) fij(l)

(90)

where we assume

N å j=1  aij2(l) = |xi(l)|2 = pi

(91)

This leads to

di(l) = N å j=1  aij2(l) (lij(l) - liN(l))

(92)

Since all terms in the sum are non-negative we must have

di(l) ³ aij2(l) (lij(l) - liN(l))

(93)

for j=1,2,¼,N. Now suppose via equation (93) we define e_ij(l) £ d_i(l) as

eij(l) = aij2(l)(lij(l) -liN(l))

(94)

Dividing by nonzero a_ij(l) results in

eij(l) aij(l) = aij(l)lij(l)-aij(l)liN(l)

(95)

To see how closely each s_i(l) approximates an eigenvector of R(l) = R_i(l) + s_i(l)s_i^T(l) the signal plus noise covariance matrix at iteration l, we form the product

R(l) si(l) = å j Î Ji(l)  lij(l) aij(l) fij(l)+pi å j Î Ji(l)  aij(l) fij(l)

(96)

where J_i(l) is the set of all j such that a_ij(l) ¹ 0. Using equation (95) in equation (96) yields

R(l) si(l) = å j Î Ji(l)  æ è  eij(l) aij(l) + liN(l) aij(l) ö ø fij(l)+pi å j Î Ji(l)  aij(l) fij(l)

(97)

Regrouping we have

R(l)si(l) = (liN(l) + pi)si(l)+ å j Î Ji(l)   eij(l) aij(l) fij(l)

(98)

However, since lim_{l® ¥} d_i(l) = 0 and a_ij²(l) < p_i, then for any lim_{l® ¥} a_ij(l) ¹ 0 we must have by equation (94)

lim l® ¥  lij(l) - liN(l) = 0

(99)

Therefore, we have

lim l® ¥   eij(l) aij(l) = lim l® ¥  aij(l)( lij(l) - liN(l) ) = 0

(100)

for any a_ij(l) which does not approach zero.

Thus, we can choose l such that the terms e_ij(l) are arbitrarily small. This implies that for suitably large l, all codewords s_i(l) are arbitrarily close to being eigenvectors of R(l), thus completing the proof.

We define such codeword convergence as convergence in class.  ·

Of course, Theorem 14 is mute on the relative values of the l_iN(l) + p_i which define classes. We thus have the following corollary, stated without proof:

Corollary 2 With greedy+ interference avoidance, codewords might not necessarily converge to a set of optimal classes, but could theoretically become trapped in local TSC minima corresponding to a suboptimal set of classes.

We can now formalize the greedy interference avoidance algorithm by adding an additional step.

4. Stop if "s_i and some suitably small threshold n > 0 we have


| å j Î Ji(l)   eij(l) aij(l) fij(l)| < n