A Survey on Surrogate Approaches to Non-negative Matrix Factorization

Motivated by applications in hyperspectral imaging, we investigate methods for approximating a high-dimensional non-negative matrix Y by a product of two lower-dimensional, non-negative matrices K and X. This so-called non-negative matrix factorization is based on defining suitable Tikhonov functionals, which combine a discrepancy measure for Y ≈KX with penalty terms for enforcing additional properties of K and X. The minimization is based on alternating minimization with respect to K and X, where in each iteration step one replaces the original Tikhonov functional by a locally defined surrogate functional. The choice of surrogate functionals is crucial: It should allow a comparatively simple minimization and simultaneously its first-order optimality condition should lead to multiplicative update rules, which automatically preserve non-negativity of the iterates. We review the most standard construction principles for surrogate functionals for Frobenius-norm and Kullback–Leibler discrepancy measures. We extend the known surrogate constructions by a general framework, which allows to add a large variety of penalty terms. The paper finishes by deriving the corresponding alternating minimization schemes explicitly and by applying these methods to MALDI imaging data. © 2018, The Author(s).