In this chapter we consider the singular value decomposition (SVD)
of the by
matrix
. We assume without loss of generality
that
; if
consider
.
As described in §2.4, this decomposition
may be written
may also be written
or
for
.
may also be written
or
for
and
for
.
There are several ``smaller'' versions of the SVD that are
often computed.
Let
be an
by
matrix
of the first
left singular vectors,
be an
by
matrix
of the first
right singular vectors,
and
be a
by
matrix of the first
singular values.
Then we have the following SVD types.
The thin SVD may also be written
.
Each
is called a singular triplet.
The compact and truncated SVDs may be written similarly
(the sum going from
to
, or
to
, respectively).
The SVD of is closely related to the eigendecompositions of
three related Hermitian matrices,
,
, and
,
which were described in §2.4.7.
Most iterative algorithms for the SVD amount to applying an algorithm
from Chapter 4
to one of these Hermitian matrices, so we review and expand
that material here.
The choice of
,
, or
depends on which singular
values and vectors one is interested in computing.
The cost of some algorithms, like shift-and-invert (see below),
may different significantly for
,
, and
.
Thus, if we find the eigenvalues and eigenvectors
of
, then we can recover the compact SVD of
by taking
for
,
the right singular vectors as
for
,
and the first
left singular vectors by
.
The left singular vectors
through
are not determined directly, but may be taken
as any
orthonormal vectors also orthogonal to
through
.
When
is very small, i.e.,
,
then
will not be determined very accurately.
Thus, if we find the eigenvalues and eigenvectors
of
, then we can recover the compact SVD of
by taking
for
, the left singular vectors
as
for
, and the
first
right singular vectors as
.
The right singular vectors
through
are
not determined directly, but may be taken as any
orthonormal
vectors also orthogonal to
through
.
When
is very small, i.e.,
,
then
will not be determined very accurately.
We note that
The correspondence between the SVD of and the eigendecomposition
of
shows that the discussion of perturbation theory for
eigenvalues and eigenvectors of Hermitian matrices in
§4.1 and
§4.8 applies directly to the SVD, as we now describe.
Perturbing to
can change the singular values by
at most
:
Now suppose
is an approximation
of the singular triplet
, where
and
are unit vectors. The ``best''
corresponding to
and
is the Rayleigh quotient
, so we assume that
has this value. Suppose
is closer
to
than any other
, and let
be the
gap
between
and any other singular value:
.
The difference between and
is
bounded by
is easy to compute given
,
, and
,
but
requires more information about the singular values
in order to approximate it. Typically one uses the computed
singular values near
to approximate
:
,
where
is the next computed singular value smaller than
, and
is the next computed
singular value larger than
.