126 Handb ook of Big Data
and mathematically equivalent to the symmetric IRAM. Harnessing these connections led
to the development of the IRLBA, a simple, powerful, and computationally fast partial
SVD method.
Shortly after developing the IRLBA, Baglama and Reichel [3] extended the method to
work with the block form of the GKLB procedure [10] and published MATLAB
computer
codes irlba and irlbablk [2]. Block methods are advantageous when computing multiple
or clustered singular values and can utilize Level 3 BLAS matrix–matrix products. Also,
block methods are favorable when matrices are so large that they have to be retrieved from
disk when matrix–vector products with them are to be evaluated. However, there are added
complexities to a block method, for example, linear dependence of blocks and block size.
We will not discuss block methods in this chapter.
Recently, additional software packages for the IRLBA were developed in the program-
ming languages R and Python. Lewis [23] developed The irlba Package in the open
source statistical programming language R and Kane and Lewis [17] created irlbpy,
an implementation of the IRLBA in Python for Numpy. See Section 8.4 for examples
demonstrating the performance of the software implementations.
Baglama and Reichel [1] developed two strategies: augmentation with Ritz vectors
irlba(R) for finding the largest (and smallest) singular triplets and augmentation with
harmonic Ritz vectors irlba(H) for finding the smallest singular triplets. When seeking
to compute the smallest singular triplets of a matrix, augmentation by harmonic Ritz
vectors, irlba(H), often yielded faster convergence. This method will not be described
in this chapter since our focus is in the context of large data and on computing the largest
singular triplets; therefore, we refer the reader to [1] for details on irlba(H). In this chapter,
we will refer to irlba(R) as IRLBA.
8.2 GKLB Procedure
Let A ∈ R
×n
be a large sparse matrix. We may assume that ≥ n, because otherwise
we replace the matrix by its transpose. Let u
i
∈ R
and v
i
∈ R
n
denote the left and right
singular vectors of A associated with the singular value σ
i
. Define U
n
=[u
1
,u
2
,...,u
n
] ∈
R
×n
and V
n
=[v
1
,v
2
,...,v
n
] ∈ R
n×n
with orthonormal columns, as well as Σ
n
=
diag[σ
1
, σ
2
,...,σ
n
] ∈ R
n×n
.Then
AV
n
= U
n
Σ
n
and A
T
U
n
= V
n
Σ
n
(8.1)
are the SVD of A and A
T
, respectively. We assume the singular values are ordered,
σ
1
≥ σ
2
≥ ...≥ σ
n
≥ 0, (8.2)
and refer to {σ
i
,u
i
,v
i
} as a singular triplet of A.
We are interested in approximating the k largest singular triplets {σ
i
,u
i
,v
i
}
k
i=1
.Letthe
matrices U
k
∈ R
×k
and V
k
∈ R
n×k
consist of the first k columns of the matrices U
n
and
V
n
in the SVD (Equation 8.1) of A, and introduce Σ
k
= diag[σ
1
,...,σ
k
] ∈ R
k×k
. Then,
analogously to Equation 8.1, we have the partial SVD
AV
k
= U
k
Σ
k
and A
T
U
k
= V
k
Σ
k
. (8.3)
The approximations to Equation 8.3 can be obtained from projections onto Krylov subspaces
K
m
(A
T
A, p
1
)=span{p
1
,A
T
Ap
1
, (A
T
A)
2
p
1
,...,(A
T
A)
m−1
p
1
},
K
m
(AA
T
,q
1
)=span{q
1
,AA
T
q
1
, (AA
T
)
2
q
1
,...,(AA
T
)
m−1
q
1
},
(8.4)
with initial vectors p
1
and q
1
= Ap
1
/Ap
1
, respectively. Throughout this discussion, ·
denotes the Euclidean vector norm as well as the associated induced matrix norm.