Algorithms for Non-Negative Matrix Factorization – Short Science Summary:


This paper analyzes two separate iterative methods for calculating NMF decompositions: one that minimizes least-squares error and one that minimizes generalized KL-divergence.

The cost functions given for the two methods are as follows:

Least-squares error:
||A – B||^2 = ∑_(ij) (Aij*Bij)^2

Divergence:
D(A||B) = ∑_ij (Aij log⁡(Aij/Bij) - Aij+Bij)

The authors found that using the below multiplicative update rules for each iteration of the corresponding optimization algorithm results in a good compromise between run speed and ease of implementation:

[Thm 1]

[Thm 2]

The authors go on to prove convergence to at least a locally optimal solution for both of the above choices of cost function.