Database Reference
In-Depth Information
with the desired matrix
V
k
of right singular vectors. As described at the outset, given
this matrix, the corresponding matrices of singular values
S
k
and left singular
vectors
U
k
may easily be established.
A
Galerkin method
yields an approximate solution of (
8.22
) by imposing the
additional constraint
ranX
Q
R
n
for a suitable subspace Q satisfying
k
dim
Q ¼ l
<<
n.
It can be shown that this amounts to solving
tr Y
T
Q
T
GQY
max
Y
∈R
ð
8
:
23
Þ
,
ln
Y
T
Y¼I
for some Q satisfying
ran Q ¼
Q,
Q
T
Q ¼ I
.
A
Krylov space method
recursively computes nested orthogonal bases
Q
1
,
,
Q
l
of subspaces Q
1
...
Q
l
yet to be specified and a sequence of
approximate solutions
X
l
,
k l n
of (
8.22
) given by
X
l
:
¼ Q
l
Y
l
,
where
Y
l
is an
optimizer of (
8.23
) for
Q ¼ Q
l
.
For an initial vector
q
1
,
...
the subspaces are
established as follows:
Q
l
:¼ K
l
G
ð
;
q
1
Þ
,
l
f
1
; ...;
n
g,
∈
where
Þ¼range q
1
,
Gq
1
,
G
2
q
1
,
,
G
l
1
q
1
K
l
G
ð
;
q
1
...
is called
l
th
Krylov space
of
G
and
q
1
. The
Lanczos process
is a recursive procedure
for the computation of the basis vectors
q
l
, which are also referred to as
Lanczos
vectors.
Algorithm 8.2 Lanczos process
Input:
G
,
q
1
,
l
Output:
q
1
,
α
i
0
s
,
β
i
0
s
...
,
q
l
+1
,
1:
β
1
:
¼
0,
q
0
¼
0
2:
for
i ¼ 1
,
...
,
l
do
3:
w
i
:
¼ Gq
i
β
i
q
i
1
4:
α
i
:
¼hw
1
,
q
i
i
5:
w
i
:
¼ w
i
α
i
q
i
6:
β
i
+1
:
¼kwk
2
β
i
+1
¼
0 then
8: stop
9: end if
10:
q
i
+1
:
¼ w
i
/
7:
if
β
i
+1
11: end for
