Non-negative Matrix Factorization - Algorithms

Algorithms

There are several ways in which the W and H may be found: Lee and Seung's multiplicative update rule has been a popular method due to the simplicity of implementation. Since then, a few other algorithmic approaches have been developed.

Some successful algorithms are based on alternating non-negative least squares, in which the nonnegativity constrained least squares subproblems are iteratively solved. Specific approaches include the projected gradient descent methods, the active-set method, and the block principal pivoting method among several others.

The currently available algorithms are sub-optimal as they can only guarantee finding a local minimum, rather than a global minimum of the cost function. A provably optimal algorithm is unlikely in the near future as the problem has been shown to generalize the k-means clustering problem which is known to be computationally difficult (NP-complete). However, as in many other data mining applications a local minimum may still prove to be useful.

Arora, Ge, Kannan, and Moitra (2012) have given an algorithm for exact NMF that provably runs in polynomial-time (i.e., always halts with the correct answer) if one of the factors W satisfies the separability condition. This condition is observed to hold in factorizations empirically found in many settings. They also give a more precise analysis of the complexity of NMF as a function of the dimension of W and H.