Nonnegative matrix factorization based on linear complementarity problem

Based on the KKT conditions of the nonnegativity constrained least squares which are gotten by fixing one variant matrix in a nonnegative matrix factorization (NMF) optimization problem, a linear complementarity problem (LCP) is obtained. Then a new algorithm for NMF based on LCP is proposed and its convergence is proved. And then a practical algorithm is presented to simplify the algorithm´s implementation complexity. The experiments show that the new algorithm converges faster than the classical multiplicative update algorithm and the projected gradient algorithm.