Digital Signal Processing Reference
In-Depth Information
Table 13.4
Golub-Kahan algorithm for SVD
function
[
u
,σ
]
=
houszero
(x)
function
[
c
,
s
,
r
]
=
rot
(f,g)
m
=
max
(
|
x
i
|
),
i
=
1
,
2
,...,
n
if
f
=
0then
c
=
0;
s
=
1;
r
=
g
x
i
m
u
i
=
,
i
=
1
,
2
,...,
n
elseif (
|
f
|
>
|
g
|
)then
=
√
1
g
f
1
tt
sign
(
0
)
=
1
t
=
;
tt
+
t
2
;
c
=
;
s
=
t
.
c
;
r
=
tt
.
f
u
1
2
σ
=
sign
(
u
1
)
+
u
2
2
+···+
u
n
2
else
√
1
f
g
1
tt
t
2
u
1
=
u
1
+
σ
t
=
;
tt
=
+
;
s
=
;
c
=
t
.
s
;
r
=
tt
.
g
σ
=−
m
.σ
endif
end
houszero
end
rot
Golub-Kahan algorithm for SVD
…
U
1
=
I
,
V
1
=
I
repeat
for
k
=
1
:
(
n
−
1
)
for
i
=
1
:
(
n
−
1
)
[
u
,σ
]=
houszero
(
A
(
k
:
m
,
k
)
U
2
=
I
2
uu
T
u
T
u
H
1
=
I
−
[
c
,
s
,
r
]=
rot
(
A
(
i
,
i
),
A
(
i
,
i
+
1
)
)
P
1
=
I
Q
=
I
cs
−
sc
P
1
(
k
:
m
,
k
:
n
)
=
H
1
Q
(
i
:
i
+
1
,
i
:
i
+
1
)
=
AQ
T
A
(
k
:
m
,
k
:
n
)
=
H
1
.
A
(
k
:
m
,
k
:
n
)
A
=
Q
T
U
1
=
U
1
.
P
1
V
2
=
V
2
.
if
k
≤
(
n
−
2
)
[
c
,
s
,
r
]=
rot
(
A
(
i
,
i
),
A
(
i
+
1
,
i
)
)
T
)
[
v, σ
]=
houszero
(
A
(
k
,
k
+
1
:
n
)
Q
=
I
cs
−
T
H
2
=
I
−
2
vv
Q
(
i
:
i
+
1
,
i
:
i
+
1
)
=
v
T
v
sc
P
2
=
I
A
=
QA
P
2
(
k
:
m
−
1
,
k
:
n
−
1
)
=
H
2
U
2
=
U
2
.
Q
A
(
k
:
m
,
k
+
1
:
n
)
=
A
(
k
:
m
,
k
+
1
:
n
).
H
2
endfor
V
1
=
V
1
.
P
2
Σ
=
abs
(
A
)
U
T
endif
=
U
1
.
U
2
endfor
V
=
V
1
.
V
2
contd …
produce a diagonal matrix.In this process, the eigenvalues or singular values remain
same as that of the original dense symmetric matrix. Householder or Givens method
may be applied for Hessenberg reduction. We have used Givens method to produce
symmetric tridiagonal matrix (Table
13.5
).
Lanczos method is useful to transform a symmetric dense matrix to a symmetric
tridiagonal matrix. This method suffers from loss of orthogonality among Lanczos
vectors with increased number of iterations. For this reason reorthogonalization is
required to obtain proper orthogonal vectors.
Symmetric QL and QR iteration
This is an iterative process and has a complexity
of
O
n
2
. After reducing the dense symmetric matrix into its tridiagonal form by
orthogonal similarity transformation, symmetric QL or QR iteration is performed
depending on which of the first and last diagonal elements of the symmetric tridi-
agonal matrix is larger. If the first diagonal entry is larger than the last one, QR is
called upon to perform, else QL is called.
(
)
