Decomposition in Transition: Adaptive Matrix Factorization - Realtime Data Mining - page 162

Fig. 8.3 Graphical
comparison of prediction
rates: adaptive SVD with
variable rank

18

16

14

12

10

Clicks
Baskets
Orders

8

6

4

2

0

0 10 20 30

Rank

8.4 More Matrix Factorizations

8.4.1 Lanczos Methods

Lanczos methods are projection methods and are types of Krylov space methods.
Although they are not adaptive, we shall yet address them in more detail, as they
are, arguably, the most efficient solvers for eigen- and singular value decomposi-
tions and, apart from that, may provide an alternative to the projection approxima-
tions from Sect. 8.3.3 , which is even more efficiently computable. Furthermore, the
Lanczos process may be deployed for efficient computation of an initial rank-k
SVD on historical data, which may then serve as a starting point for our adaptive
SVD. There is a vast amount of Lanczos-type methods. We shall restrict ourselves
to the symmetric Lanczos algorithm.
As we have shown in Sect. 8.3.1 , for an arbitrary matrix A, we may establish the
Gramian matrix G ¼ A T A, which is symmetric and positive semidefinite, so as to
compute an SVD ( 8.13 )of A through an eigenvalue decomposition (EVD, i.e.,
spectral decomposition ( 8.9 )) of G by means of ( 8.11 ) and ( 8.12 ). This, of course,
similarly applies to the truncated SVD ( 8.14 ). Thus, we need an efficient method for
the computation of a truncated EVD of symmetric positive semidefinite matrices at
the core. This requirement is best met by the symmetric Lanczos algorithm, as it is
especially suitable for large eigenvalues, which are needed for the truncated SVD.
Let G

nn be a symmetric positive definite matrix of order n . Then we
seek after an optimizer of

∈ S ¼o

:

tr X T GX max ð 8 : 22 Þ

,

nk

X T X¼I X ∈R

It is well known that V k is an optimizer of ( 8.22 ) if and only if ranV k , i.e., the
range or image of V k is an invariant subspace of G with respect to its k -largest
eigenvalues. Thus, we solve ( 8.22 ) to determine a matrix the columns of which are
eigenvectors of G corresponding to its k- largest eigenvalues. This matrix coincides