non-negative matrix factorization

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 DF W, where the elements of F and W are also all non-negative.

Algorithms for computing NMF

More background on the algorithms used can be found in Berry et al. (2007)

The algorithms fall into three general classes:

1. Multiplicative updates,
2. Alternating Least squares,
3. Projected Gradient.

Multiplicative Updates

    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.

Alternating Least Squares

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