PASTd Algorithm

PASTd Algorithm

Let be a random vector with autocorrelation matrix C_r = E{r[i]r[i]^H}. Consider the scalar function

Equation 2.150

with a matrix argument (r < N). It can be shown that [586]:

• W is a stationary point of if and only if W = U_r Q, where contains any r distinct eigenvectors of C_r and is any unitary matrix.

• All stationary points of are saddle points except when U_r contains the r dominant eigenvectors of C_r. In that case, attains the global minimum.

Therefore, for r = 1, the solution of minimizing is given by the most dominant eigenvector of C_r. In real applications, only sample vectors r[i] are available. Replacing (2.150) with the exponentially weighted sums yields

Equation 2.151

where 0 < b < 1 is a forgetting factor. The key issue of the PASTd (projection approximation subspace tracking with deflation) approach is to approximate W[i]^H r[n] in (2.151), the unknown projection of r[n] onto the columns of W[i], by y[n] = W[n – 1]^H r[n], which can be calculated for 1 n i at time i. This results in a modified cost function

Equation 2.152

The recursive least-squares (RLS) algorithm can then be used to solve for the W[i] that minimizes the exponentially weighted least-squares criterion (2.152).

The PASTd algorithm for tracking the eigenvalues and eigenvectors of the signal subspace is based on the deflation technique and can be described as follows. For r = 1, the most dominant eigenvector is updated by minimizing in (2.152). Then the projection of the current data vector r[i] onto this eigenvector is removed from r[i] itself. Now the second most dominant eigenvector becomes the most dominant one in the updated data vector and it can be extracted similarly. This procedure is applied repeatedly until all the K eigenvectors are estimated sequentially.

Based on the estimated eigenvalues, using information theoretic criteria such as the Akaike information criterion (AIC) or the minimum description length (MDL) criterion [557], the rank of the signal subspace, or equivalently, the number of active users in the channel, can be estimated adaptively as well [585]. The quantities AIC and MDL are defined as follows:

Equation 2.153

Equation 2.154

Equation 2.155

The AIC (respectively, MDL) estimate of subspace rank is given by the value of k that minimizes the quantity (2.153) [respectively, (2.154)]. Finally, the PASTd algorithm for both rank and signal subspace tracking is summarized in Table 2.1. The computational complexity of this algorithm is operations per update. The convergence dynamics of the PASTd algorithm are studied in [587]. It is shown there that with a forgetting factor b = 1, under mild conditions, this algorithm converges globally and almost surely to the signal eigenvectors and eigenvalues.

Example 1: Performance Comparison Between Subspace and MOE Blind Detectors This example compares the performance of the subspace-based blind MMSE detector with the performance of the MOE blind adaptive detector. It assumes a real-valued synchronous CDMA system with a processing gain N = 31 and six users (K = 6). The desired user is user 1. There are four 10-dB multiple-access interferers (MAIs) and one 20-dB MAI (i.e., = 10 for k = 2, ..., 5 and = 100 for k = 6). The performance measure is the output SINR. For the PASTd subspace tracking algorithm, we found that with a random initialization, the convergence is fairly slow. Therefore, in the simulations, the initial estimates of the eigencomponents of the signal subspace are obtained by applying an SVD to the first 50 data vectors. The PASTd algorithm is then employed thereafter for tracking the signal subspace. The time-averaged output SINR versus number of iterations is plotted in Fig. 2.10.

[a] The rank estimation is based on the Akaike information criterion.

As a comparison, the simulated performance of the recursive least-squares (RLS) version of the MOE blind adaptive detector is also shown in Fig. 2.10. It has been shown in [389] that the steady-state SINR of this algorithm is given by

Equation 2.156

where SINR^* is the output SINR value of the exact linear MMSE detector, and is the forgetting factor). Hence the steady-state SINR performance of this algorithm is upper bounded by 1/d. This behavior can be observed in Fig. 2.10. Although an analytical expression for the steady-state SINR of the subspace-based blind adaptive detector is very difficult to obtain, as the dynamics of the subspace tracking algorithms are fairly complicated, it is seen from Fig. 2.10 that with the same forgetting factor, the subspace blind adaptive detector well outperforms the RLS MOE detector. Moreover, the RLS MOE detector has a computational complexity of per update, whereas the complexity per update of the subspace detector is

Example 2: Tracking Performance in a Dynamic Environment This example illustrates the performance of the subspace blind adaptive detector in a dynamic multiple-access channel, where interferers may enter or exit the channel. The simulation starts with six 10-dB MAIs in the channel; at t = 2000, a 20-dB MAI enters the channel; at t = 4000, the 20-dB MAI and three of the 10-dB MAIs exit the channel. The performance of the proposed detector is plotted in Fig. 2.11. It is seen that this subspace-based blind adaptive multiuser detector can adapt fairly rapidly to the dynamic channel traffic.