Digital Signal Processing Reference
In-Depth Information
The diagonal elements of
D
are called
eigenvalues
and arranged in decreasing
order, satisfy
l
1
l
n
.
0, while the orthogonal columns (
u
i
)
i¼
1,
...
,
n
of
U
are the corresponding unit 2-norm
eigenvectors
of
C
.
For the sake of simplicity, only real-valued data will be considered from the next
subsection and throughout this chapter. The extension to complex-valued data is
often straightforward by changing the transposition operator to the conjugate transpo-
sition one. But we note two difficulties. First, for simple
2
eigenvalues, the associated
eigenvectors are unique up to a multiplicative sign in the real case, but only to a unit
modulus constant in the complex case, and consequently a constraint ought to be
added to fix them to avoid any discrepancies between the statistics observed in numeri-
cal simulations and the theoretical formulas. The reader interested by the conse-
quences of this nonuniqueness on the derivation of the asymptotic variance of
estimated eigenvectors from sample covariance matrices (SCMs) can refer to [34],
(see also Exercise 4.1). Second, in the complex case, the second-order properties
of multidimensional zero-mean random variables
x
are not characterized by the com-
plex Hermitian covariance matrix E(
xx
H
) only, but also by the complex symmetric
complementary covariance [58] matrix E(
xx
T
).
The computational complexity of the most efficient existing iterative algorithms
that perform EVD of real symmetric matrices is cubic by iteration with respect to
the matrix dimension (more details can be sought in [35, Chap. 8]).
4.2.2 QR Factorization
The QR factorization of an
n r
real-valued matrix
W
, with
n r
is defined as
(see e.g. [37, Sec. 2.6])
W¼QR ¼Q
1
R
1
(4
:
2)
where
Q
is an
n n
orthonormal matrix,
R
is an
n r
upper triangular matrix, and
Q
1
denotes the first
r
columns of
Q
and
R
1
the
r r
matrix constituted with
the first
r
rows of
R
.If
W
is of full column rank, the columns of
Q
1
form an
orthonormal basis for the range of
W
. Furthermore, in this case the skinny factoriz-
ation
Q
1
R
1
of
W
is unique if
R
1
is constrained to have positive diagonal entries.
The computation of the QR decomposition can be performed in several ways.
Existing methods are based on Householder, block Householder, Givens or fast
Givens transformations. Alternatively, the Gram-Schmidt orthonormalization
process or a more numerically stable variant called modified Gram-Schmidt can be
used. The interested reader can seek details for the aforementioned QR imple-
mentations in [35, pp. 224-233]), where the complexity is of the order of
O
(
nr
2
)
operations.
2
This is in contrast to multiple eigenvalues for which only the subspaces generated by the eigenvectors
associated with these multiple eigenvalues are unique.
Search WWH ::
Custom Search