Database Reference
In-Depth Information
nl
, it may easily be shown that
With
Q
l
:¼ q
1
; ...;
½
q
l
∈R
2
3
α
1
β
2
4
5
β
2
α
2
β
3
⋱⋱ ⋱
β
l
1
Q
l
GQ
l
¼ T
l
¼
:
ð
8
:
24
Þ
α
l
1
β
l
β
l
α
l
An eigenvalue of
T
l
is called
Ritz value,
and, for a corresponding eigenvector
y
l
,
x
l
:
¼ Q
l
y
l
is called
Ritz vector
. With
l
increasing, more and more Ritz values and
vectors converge to eigenvalues and vectors of
G
. Thus, the eigenvectors
y
l
yield
the desired solution of (
8.23
), i.e.,
Y
l
:
¼
[
y
1
,
,
y
l
]
,
from which we obtain the
approximate solution of (
8.22
). Due to the simplicity of the tri-diagonal matrix
T
l
,
the eigenproblem (
8.23
) may be solved efficiently, e.g., by simple subspace itera-
tion procedures.
Although the demonstrated Lanczos method looks fairly simple, it bears several
difficulties. These include the problem of orthogonality. In practice (i.e., finite
precision arithmetic), the theoretical orthogonality of the computed Lanczos
vectors
q
l
is lost at an early stage due to inevitable rounding errors. Hence, many
approaches to
re-orthogonalization
of Lanczos vectors have emerged. The easiest
approach consists in orthogonalizing each newly obtained vector with respect to the
previous basis. This is accomplished by adding the following line immediately
below line 5 of the pseudo-code:
...
:¼ w
i
X
i
1
w
i
j¼
1
<
w
i
,
q
j
>
q
j
:
This additional step of complete re-orthogonalization increases the computa-
tional load by
O
(
l
2
n
), but ensures that all Lanczos vectors be numerically mutually
orthogonal and thus all subsequent processes be stable. Since, with regard to our
factorization, we are interested only in the
k n
largest eigenvalues,
l
is not too
large in practice (at most some 100). Hence, complete re-orthogonalization does not
cause any trouble at all.
Another difficulty of the Lanczos method is that it may not find all eigenvalues,
even if the computation is carried out in exact arithmetic. This problem occurs
predominantly for small eigenvalues. To remedy this problem as well, many
elaborate approaches have been developed. With respect to large eigenvalues,
however, which we are predominantly interested in, the Lanczos process works in
a fairly stable fashion. Altogether, we see that for our application, it is not necessary
to put much effort into stabilization.
Thus, we may use the Lanczos method to compute the truncated SVD, which, in
turn, provides the right- or left-projection approximation (
8.19
)or(
8.20
), respec-
tively, for determining the recommendations.
Even more, in [CS09], Chen and Saad have shown how the Lanczos method may
be used for an even easier computation of the projections (
8.19
) and (
8.20
). To this
