|
The non-negative matrix factorization or NMF is a factorization of a data matrix D, whose elements are all non-negative, into a feature matrix F and a weights matrix W such that D ≈ F W, where the elements of F and W are also all non-negative.
More background on the algorithms used can be found in Berry et al. (2007)
The algorithms fall into three general classes:
initialize F and W
while iter < maxinter and not convergence
(MU) W = W .* (F'*D) ./ (F'*F*W + 10^^−9^)
(MU) F = F .* (D*W') ./ (F*W*W' + 10^^−9^)
test for convergence
endwhile
In the multiplicative update (MU) steps above "*" means ordinary matrix multiplication while ".*" and "./" mean elementwise matrix operations. The factors 10-9 guard against division by zero.
The optimization of D ≈ F*W is not convex in both F and W it is convex in either F or W. Therefor given one, the other can be found by a simple least squares (LS) algorithm. This can be done in an alternating fashion.
The Aternating Least Squares (ALS) algorithm is as follows:
initialize F
while iter < maxinter and not convergence
(LS) Solve for W in matrix equation F'*F*W = F'*D
(NONNEG) Set all negative elements in W to 0
(LS) Solve for F in matrix equation W*W'*F' = W*D'
(NONNEG) Set all negative elements in F to 0
test for convergence
endwhile
© djmw 20230801