Information Technology Reference
In-Depth Information
1.12 PARTIAL TLS ALGORITHM
Considering the TLS solution of
AX
≈
B
to be deduced from a basis of the
right singular subspace associated with the smallest singular values of [
A
;
B
],
considerable savings in computation time is possible by calculating only the basis
vectors desired. This can be done in a
direct
way by modifying the SVD algorithm
or in an
iterative
waybymakinguseofstartvectors.Animprovedalgorithm
PSVD (partial SVD) is presented in [98], which computes this singular subspace.
There are three reasons for its higher efficiency vs. the
classical
SVD [75]:
1. The Householder transformations of the bidiagonalization are applied only
to the basis vectors of the desired singular subspace.
2. The bidiagonal is only partially diagonalized.
3. An appropriate choice is made between QR and QL iteration steps [99].
Definition 38 (Motor Gap)
The
motor gap
is the gap between the singular
values associated with the desired and undesired vectors.
Depending on the motor gap (it must be large), the desired numerical accu-
racy, and the dimension of the desired subspace (it must be small), PSVD can be
three times as fast as
the classical SVD, while the same accuracy can be main-
tained. Incorporating the PSVD algorithm into the TLS computations results in
an improved
partial TLS
(PTLS) [96]. Typically, PTLS reduces the computation
time by a factor of 2.
1.13 ITERATIVE COMPUTATION METHODS
In the estimation of parameters of nonstationary systems that vary slowly with
time, space, or frequency, a priori information is available for the TLS algorithm.
Indeed, in this case, slowly varying sets of equations must be solved at each time
instant and the TLS solution at the last step is usually a good initial guess for
the solution at the next step. If the changes in these systems are of small norm
but of
full
rank (e.g., when all elements of the data matrix change slowly from
step to step), the computation time can be better reduced by using an
iterative
method. There are also other advantages in using this type of algorithm:
• Each step supplies a new and better estimate of the solution, permitting us
to control the level of convergence depending on the perturbations of the
data.
• It is easy to code.
• Some iterative routines use the given matrix over and over again without
modification, exploiting its particular structure or sparsity.
Search WWH ::
Custom Search