Relaxation-Constraint Algorithm For Nonnegative Matrix Factorization

Nonnegative maxtirx factorization is a new unsupervised machine learning technique that can keep the nonnegativity.There are two kinds of methods used in conventional NMF algorithms to keep nonnegativity.The first kind combines the operations that keep the nonnegativity of data,such as matrix multipication and element-wised multiplication a to form an algorithm.Such algorithms often suffer from slow convergence or big reconstruction error problems.The second kind of methods can use all kinds of operations freely.But these algorithms have to add a process to force the negative elements to zero,known as projection.The projection step makes the analysis of convergence much more difficult,and even makes an algorithm unstable.Two different new algorithms named relaxation-constraint NMF and weak-constraint NMF are proposed to deal with the problems mentioned above.Relaxation-constraint NMF is a new algorithm that carries out the nonnegativity constraint after numerical computation.It divides NMF problem into two sub-problems.At the relaxation stage,a real-valued matrix factorization is calculated.At the constraint stage,it transforms the real-valued factorization to nonnegative factorization by proper means.An adaptive gradient descent method is proposed to solve the relaxation problem.For the problems in the constraint stage,the determination condition of nonnegatizable is made clear.An algorithm is especially designed for rank=2,and an approximation algorithm is designed for rank higher than 2.The weak-constraint NMF is a new algorithm,which implements the nonnegativity constraint gradually in the whole process of numerical computation.By introducing the concept of nonnegativity constraint intensity,the nonnegativity constraint is quantified.It greatly simplifies NMF algorithm design that by adding a weak-constraint step,a realvalued matrix factorization algorithm can be changed into an NMF algorithm.Basing on this,an NMF algorithm named ACNMF if proposed.Weak-constraint NMF algorithm is a generalized approach for all rank.The reconstruction error is significantly smaller than the conventional methods.