Database Reference
In-Depth Information
Theorem 8.1 states that the truncated SVD provides the best matrix factorization
with respect to quality of approximation. In general, however, this goes along with a
loss of stochasticity of the matrix of transition probabilities
P
:¼ P
k
.
Hence, we require, on one hand, that the factorized transition probabilities
satisfy
p
ss
0
1,
8s
,
s
0
0
e
∈
S
:
ð
8
:
26
Þ
On the other hand, the truncated SVD also violates the row sum condition (3.2).
Thus, we furthermore require
X
s
0
p
ss
0
¼
1
8s
∈
S
:
ð
8
:
27
Þ
It is possible to impose the conditions (
8.26
) and (
8.27
) by subsequent normal-
ization of the factorization (
8.14
). Although this may look somewhat artificial at the
first glance, one must take into account that violation of stochasticity by a rank-
k
approximation has no deeply rooted causes with respect to content. And the
truncated SVD is still the best approximation.
An alternative remedy consists in using specific nonnegative matrix factoriza-
tions, which we shall consider in the next section.
8.4.3 Nonnegative Matrix Factorizations
In a nonnegative matrix factorization (NMF), we consider the problem (
8.1
) for a
nonnegative matrix
A
and require that the factor matrices
X, Y,
as well, be nonneg-
ative. With regard to the Frobenius norm, we obtain the following problem
statement:
2
F
,
X
,
Y
0
min
k
A XY
k
:
ð
8
:
28
Þ
,
mk
kn
X
∈R
Y
∈R
As compared with the SVD-based approach, this gives rise to certain advantages
for nonnegative
A
. Most importantly, the matrices
X,Y
have a clear interpretation -
as opposed to the SVD. If we consider the columns of the left factor
X
as basis
vectors, i.e.,
X ¼ x
1
½
j
...
jx
k
,
then the columns of
A
,
A ¼ a
1
½
j
...
ja
m
,
are approximately expressed in terms of the basis
B
X
:
¼
{
x
1
,
...
,
x
k
}:
a
j
x
1
y
1
j
þ ...þ x
k
y
kj
,1
j n
:
