Contents

# Singular Value Decomposition: LAPACK Computational Routines

This
topic
describes LAPACK routines for computing the singular value decomposition (SVD) of a general
m
-by-
n
matrix
A
:
A
=
U
Σ
V
H
.
In this decomposition,
U
and
V
are unitary (for complex
A
) or orthogonal (for real
A
);
Σ
is an
m
-by-
n
diagonal matrix with real diagonal elements
σ
i
:
σ
1
σ
2
...
σ
min(
m
,
n
)
0
.
The diagonal elements
σ
i
are singular values of
A
. The first
min(
m
,
n
)
columns of the matrices
U
and
V
are, respectively, left and right singular vectors of
A
. The singular values and singular vectors satisfy
Av
i
=
σ
i
u
i
and
A
H
u
i
=
σ
i
v
i
where
u
i
and
v
i
are the
i
-th columns of
U
and
V
, respectively.
To find the SVD of a general matrix
A
, call the LAPACK routine
?gebrd
or
?gbbrd
for reducing
A
to a bidiagonal matrix
B
by a unitary (orthogonal) transformation:
A
=
QBP
H
. Then call
?bdsqr
, which forms the SVD of a bidiagonal matrix:
B
=
U
1
Σ
V
1
H
.
Thus, the sought-for SVD of
A
is given by
A
=
U
Σ
V
H
=(
QU
1
)
Σ
(
V
1
H
P
H
)
.
Table
"Computational Routines for Singular Value Decomposition (SVD)"
lists LAPACK routines that perform singular value decomposition of matrices.
Computational Routines for Singular Value Decomposition (SVD)
Operation
Real matrices
Complex matrices
Reduce
A
to a bidiagonal matrix
B
:
A
=
QBP
H
(full storage)
Reduce
A
to a bidiagonal matrix
B
:
A
=
QBP
H
(band storage)
Generate the orthogonal (unitary) matrix
Q
or P
Apply the orthogonal (unitary) matrix
Q
or P
Form singular value decomposition of the bidiagonal matrix
B
:
B
=
U
Σ
V
H
Decision Tree: Singular Value Decomposition
Figure "Decision Tree: Singular Value Decomposition" presents a decision tree that helps you choose the right sequence of routines for SVD, depending on whether you need singular values only or singular vectors as well, whether
A
is real or complex, and so on.
You can use the SVD to find a minimum-norm solution to a (possibly) rank-deficient least squares problem of minimizing
||
Ax
-
b
||
2
. The effective rank
k
of the matrix
A
can be determined as the number of singular values which exceed a suitable threshold. The minimum-norm solution is
x
=
V
k
(
Σ
k
)
-1
c
where
Σ
k
k
-by-
k
submatrix of
Σ
, the matrix
V
k
consists of the first
k
columns of
V
=
PV
1
, and the vector
c
consists of the first
k
elements of
U
H
b
=
U
1
H
Q
H
b
.

#### Product and Performance Information

1

Intel's compilers may or may not optimize to the same degree for non-Intel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include SSE2, SSE3, and SSSE3 instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessor-dependent optimizations in this product are intended for use with Intel microprocessors. Certain optimizations not specific to Intel microarchitecture are reserved for Intel microprocessors. Please refer to the applicable product User and Reference Guides for more information regarding the specific instruction sets covered by this notice.

Notice revision #20110804