Iterative improvement of the Multiplicative Update NMF algorithm using nature-inspired optimization

Low-rank approximations of data (e. g. based on the Singular Value Decomposition) have proven very useful in various data mining applications. The Non-negative Matrix Factorization (NMF) leads to special low-rank approximations which satisfy non-negativity constraints. The Multiplicative Update (MU) algorithm is one of the two original NMF algorithms and is still one of the fastest NMF algorithms per iteration. Nevertheless, MU demands a quite large number of iterations in order to provide an accurate approximation of the original data. In this paper we present a new iterative update strategy for the MU algorithm based on nature-inspired optimization algorithms. The goal is to achieve a better accuracy per runtime compared to the standard version of MU. Several properties of the NMF objective function underlying the MU algorithm motivate the utilization of heuristic search algorithms. Indeed, this function is usually non-differentiable, discontinuous, and may possess many local minima. Experimental results show that our new iterative update strategy for the MU algorithm achieves the same approximation error than the standard version in significantly fewer iterations and in faster overall runtime.