NAHJ Subspace Tracking

NAHJ Subspace Tracking

The algorithm we present here was developed in [411, 412]. It is a member of the QR-Jacobi family in the sense that it uses Givens rotations during the updating process. However, this algorithm avoids the QR step entirely. Instead of working with the SVD-type decomposition in (2.159), we work with the eigendecomposition of the form

Equation 2.163

where S²[i] is Hermitian and almost diagonal. This is simply the eigendecomposition (2.158) except that we have relaxed the assumption that L[i] is perfectly diagonal. At each iteration we use a Householder transformation and a vector outer product to update S²[i] directly. We then use a single set of two-sided Givens rotations to partially diagonalize the resulting Hermitian matrix. There is no need for a separate QR step. Essentially, the diagonalization process used in this algorithm is a partial implementation of the well-known symmetric Jacobi SVD algorithm [176] (not to be confused with the family of QR-Jacobi update algorithms). This algorithm is used to find the eigenstructure of a general fixed symmetric matrix and is known to generate more accurate eigenvalues and eigenvectors than the symmetric QR SVD algorithm but with a higher computational complexity [313]. However, we do not perform the full sweep of K(K - 1)/2 rotations required for the symmetric Jacobi algorithm, only a carefully selected set of about K rotations. This is sufficient because the matrix that we wish to diagonalize already has much of its energy concentrated along the diagonal. This is a situation that the Jacobi algorithm can take advantage of but which the QR algorithm cannot. The Jacobi algorithm also has an inherent parallelism, which the QR algorithm does not. Table 2.2 contains a summary of this algorithm, which we term NAHJ (noise-averaged Hermitian–Jacobi) subspace tracking.

Table 2.2. NAHJ Subspace Tracking Algorithm

Given: , and Us[i - 1]

Calculate rs, un, and g according to (2.160) and (2.161). Dropping the indices, generate the modified factorization: Let Ys be the K + 2 principal submatrix of the matrix sum in step 2. Apply a sequence of r + 1 Givens rotations to Ys to produce Set equal to the K + 1 principal submatrix of Ya. Let Us[i] be composed of the first K+1 columns of Reaverage the noise power: where Let Ls[i] be the diagonal matrix whose diagonal is equal to the first K elements of the diagonal of Ya.

Algorithm

The first step in NAHJ subspace tracking is the Householder transformation mentioned previously. The second step involves generating a modified factorization that maintains the equality

Equation 2.164

Step 3 requires that we apply K + 1 Givens rotations to partially diagonalize Y_s. Ideally, we would apply these rotations to those off-diagonal elements having the largest magnitudes. However, since the off-diagonal maxima can be located anywhere in Y_s, finding the optimal set of rotations requires an search for each rotation. This leads to an complexity algorithm. To maintain low complexity we have implemented a suboptimal alternative that is simple, yet effective. Let be the vector whose outer product is used in the modified factorization of step 2. Suppose that i₀, 1 i₀ K + 2, is the index of the element in z that has the largest magnitude. The set of elements we choose to annihilate with the Givens rotations is given by . Of course, if (Y_s)_i0,j is annihilated, so is (Y_s)_j,i0. This choice of rotations is not optimal; in fact, since we retain the off-diagonal information from the previous iteration we cannot even be sure that we annihilate the off-diagonal element in Y_s with the largest magnitude. Nevertheless, we see that the technique is very simple and is somewhat heuristically pleasing. Ultimately, performance is the measure of merit, and simulations show that it performs very well. The total computational complexity of the NAHJ subspace tracking algorithm is per update.

To adapt to changes in the size of the signal subspace (number of users), the tracking algorithm must be rank-adaptive. As before, both the AIC and the MDL criteria can be used for this purpose. To use this algorithm, we must track at least one extra eigenvalue–eigenvector pair—hence the appearance of K + 1 in Table 2.2.

Simulation Example

This example compares the performance of the subspace blind adaptive multiuser detector using the NAHJ subspace tracking algorithm with that of the LMS MOE blind adaptive multiuser detector. It assumes a synchronous CDMA system with seven users (K = 7), each employing a gold sequence of length 15 (N = 15). The desired user is user 1. There are two 0-dB and four 10-dB interferers. The performance measure is the output SINR. The performance is shown in Fig. 2.12. It is seen that the subspace blind detector significantly outperforms the LMS MOE blind detector, in terms of both convergence rate and steady-state SINR. Further applications of the NAHJ subspace tracking algorithm are found in later chapters (cf. Sections 2.7.4, 3.5.2, 5.5.4, and 5.6.3). Simulations show that the NAHJ subspace tracking algorithm substantially outperforms the PASTd algorithm, especially in multipath environments. Note that both algorithms have a computational complexity of