Nonnegative Matrix and Tensor Factorization for Discussion Tracking - Text Mining: Classification, Clustering, and Applications - page 97

have unit length.) The scales in D indicate the activity of each conversation
topic over time.

5.3.1 PARAFAC-ALS
A common approach to solving Equation (5.2) is an alternating least squares
(ALS) algorithm (19; 13; 37), due to its simplicity and ability to handle
constraints. At each inner iteration, we compute an entire factor matrix while
holding all the others fixed.
Starting with random initializations for A, B, C, and D ,weupdatethese
quantities in an alternating fashion using the method of normal equations.
The minimization problem involving A in Equation (5.2) can be rewritten in
matrix form as a least squares problem (13):
mi A AZ

2

X ( m×npq ) − , (5.3)

B ) T .
The least squares solution for Equation (5.3) involves the pseudo-inverse of
Z :

where Z =( D C

A = X ( m×npq ) Z † .
Conveniently, the pseudo-inverse of Z may be computed in a special way
that avoids computing Z T Z with an explicit Z (35), so the solution to Equa-
tion (5.3) is given by:

A = X ( m×np ) ( D B )( B T B C T C D T D ) − 1 .

C ∗ ∗

is sparse, then the product X ( m×npq ) ( D

Furthermore, if X C B )maybe

computed eciently (3) without explicitly forming D B .Thus,com-

puting A essentially reduces to several matrix inner products, sparse tensor-
matrix multiplication of B, C, and D into

C

R matrix.
Analogous least-squares steps may be used to update B, C, and D .

X , and inverting an R ×

5.3.2 Nonnegative Tensor Factorization
When analyzing nonnegative data, such as scaled term frequencies, it is
desirable for the decompositions to retain the nonnegative characteristics of
the original data and thereby facilitate easier interpretation (24). Just as
with matrix factorization, it is possible to impose nonnegativity constraints
on tensor factorizations.
Several authors have considered nonnegative tensor factorizations (NTF),
and the resulting methods can be categorized into four classes of algorithms:

1. Least squares updates where all negative values are truncated to zero
(10),

2. Nonnegative least squares (10; 16),