Digital Signal Processing Reference
In-Depth Information
First, we find the algorithms that are inspired from the classic techniques of
eigenvalue decomposition/singular value decomposition (EVD/SVD) as the QR
iteration, the Jacobi algorithm, and the Lanczos algorithm [COM 90, FUH 88]. In
this family we also find the algorithms derived from the power method [GOL 89,
COM 90, KAR 84, OWS 78].
In the second family, we include the algorithms whose principle is based on the
works of Bunch
et al.
[BUN 78] that analyze the updating of a hermitian matrix
which was modified by the addition of a matrix of rank one [DEG 92, KAR 86,
SCH 89].
The last family regroups the algorithms that consider the EVD/SVD as an
optimisation problem with or without constraints: the gradient method [KAR 84,
OWS 78, YAN 95], the conjugated gradient method [YAN 89], and the Gauss-
Newton method [BAN 92, RED 82].
We should add to this classification a fourth family of “linear” methods that were
presented above (see the propagator method) as not requiring any eigenelement
decomposition and which can be made adaptive with a sensitive reduction of the
complexity [ERI 73, MAR 96, YEH 87].
Another classification of the adaptive algorithms according to their complexity
measured in number of complex operations, given the set of two multiplications and
of one addition, was proposed in [MAR 98, Chapter 14], to which the interested
reader is invited to refer. We distinguish the algorithms of complexity
O
(
M
2
)
(of the
order of
M
2
operations) and those of complexity
O
(
MP
2
)
and
O
(
MP
)
.
These
magnitude orders are to be compared to a complexity in
O
(
M
3
)
for the eigenelement
decomposition. This classification was also made in [COM 90].
However, it is necessary to keep in mind that the complexity alone is not a
criterion sufficient to choose an algorithm. We should also take into account the
convergence capacity of the algorithm (precision and velocity), its capacity of
pursuing a non-stationary environment, its stability regarding the numeric errors as
well as the hypothesis necessary to establish this algorithm. A comparison of these
algorithms was made in [MAR 98, Chapter 14].
Search WWH ::
Custom Search