Database Reference
In-Depth Information
n
m
n
n
V
n
=
m
m
m
A
U
S
Fig. 8.2 Illustration of the singular value decomposition of a matrix A. The
dotted lines
indicate
the borders of the submatrices corresponding to a truncated SVD under the assumption that A be
rank deficient. Please note that all entries of S other than those indicated by the diagonal
solid line
are zero
orthogonal basis for the range of
A,
and {
u
r
+1
,
...
,
u
m
} for the orthogonal comple-
ment thereof. Likewise, {
v
r
+1
,
,
v
n
} span the null space of
A
, and the remaining
right singular vectors its orthogonal complement.
With regard to the solution of (
8.8
), the decisive tool is the
truncated singular
value decomposition
. It can be shown that the rank-
k
matrices
...
:¼
X
k
v
1
; ...;
T
s
j
u
j
v
j
¼ u
1
; ...;
U
k
S
k
V
k
,
k ¼
1,
A
k
½
u
k
δ
ij
s
j
½
v
k
¼:
...
,
r
j¼
1
ð
8
:
14
Þ
provide optimal rank-
k
approximations to our matrix
A
in terms of
kk
F
. In fact,
the subsequent stronger result obtains.
Theorem 8.1 (cf. Theorem 7.4.51 and Example 7.4.52 in [HJ85])
Let kkbe
a unitarily invariant norm,
i.e.
, kAk¼kQATk for any A and unitary Q,T. Then
we have
k
A B
k ¼
k
A A
k
k:
min
,
mn
B
rank B¼k
∈R
In particular, this holds for kk
F
and kk
2
,
i.e.
, the matrix norm induced by the
Euclidean norm.
As an immediate consequence, this insight provides us with a solution of the
approximation problem at hand.
Corollary 8.1
An optimal solution of
(
8.8
) is given by X
:
¼ U
d
and Y
:
¼ S
d
V
d
.
The (truncated) SVD is illustrated by Fig.
8.2
.
Example 8.4
For our web shop example 8.1, we obtain for a rank-1 approximation
immediately from our SVD
0
@
1
A
T
0
@
1
A
,
Y ¼
11
0
:
02
1
0
0
:
24
X ¼
:
2
ð
:
49
Þ
¼
ð
0
:
23
2
:
76
9
:
65
5
:
17
Þ
,
0
:
84
0
:
1
0
:
45
which coincides with the factorization in Example 8.2.
