QR-Jacobi Methods
QR-Jacobi methods constitute a family of SVD-based subspace
tracking algorithms that rely extensively on Givens rotations during the
updating process. This reduces complexity and has the advantage of maintaining
the orthogonality of matrices. Members of this family include the algorithms
presented in [340,
398, 461].
Let
Equation 2.157
denote an N x (i + 1) matrix whose columns contain the exponentially
windowed first i snapshots of the received
signal. The sample autocorrelation matrix of Y[i] and its
eigendecomposition are given by
Equation 2.158
Alternatively, the SVD of the data matrix Y[i] is given
by
Equation 2.159
where in both (2.158)
and (2.159) the columns of Us[i] contain the
eigenvectors that span the signal subspace and 
contains
the square roots of the corresponding eigenvalues. Generally speaking, SVD-based
subspace tracking algorithms attempt to track the SVD of a data matrix of
growing dimension, defined recursively as
The matrix V[i] need not be tracked. Furthermore, since the noise
subspace does not need to be calculated for the blind multiuser detection
algorithm, we do not need to track Un[i]. This allows
us to reduce complexity using noise averaging [224]. Since calculating the SVD from
scratch at each iteration is time consuming and expensive, the issue then is how
to best use the new measurement vector, r[i + 1], to
update the decomposition in (2.159).
Noise-averaged QR-Jacobi algorithms begin with a Householder
transformation that rotates the noise eigenvectors such that the projection of
the new measurement vector r[i + 1] onto the noise subspace is parallel to the first
noise vector, which we denote by un.
Specifically, let
Equation 2.160
Equation 2.161
where g
= ||r[i + 1]
- Us[i]rs ||.
Then we may write the modified factorization
Equation 2.162
where 
represents the subspace of Un[i] that is
orthogonal to un. The second step in QR-Jacobi methods,
sometimes called the QR step, involves the use of
Givens rotations to zero each entry of the measurement vector's projection onto
the signal subspace. We refer the reader to [176] for details concerning the use
of Givens matrices for this purpose. The QR step replaces the last row in the
middle matrix in the decomposition in (2.162) with zeros. These are row-type transformations
involving premultiplication of the middle matrix with a sequence of orthogonal
matrices. We do not need to accumulate these transformations in V[i] since it does
not need to be tracked.
The next step, the diagonalization step, involves at least one
set each of column and row-type rotations to further concentrate the energy in
the middle matrix along its diagonal. Sometimes called the refinement step, this is where many of the existing
algorithms begin to diverge. The algorithm in [398], for example, performs two fixed
sets of rotations in the diagonalization step but leaves the middle matrix in
upper triangular form and does not attempt a true diagonalization. This is
particularly efficient for applications that do not require a full set of
eigenvalues but is not useful here. The algorithm in [398], on the other hand, attempts to
optimize the choice of rotations to achieve the best diagonalization possible
Sections
