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 mathbfmathitY by a product of two lower-dimensional, non-negative matrices mathbfmathitK and mathbfmathitX. This so-called non-negative matrix factorization is based on defining suitable Tikhonov functionals, which combine a discrepancy measure for mathbfmathitY≈mathbfmathitKX with penalty terms for enforcing additional properties of mathbfmathitK and mathbfmathitX. The minimization is based on alternating minimization with respect to mathbfmathitK or mathbfmathitX, 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 explicitely and by applying these methods to MALDI imaging data.