Research On Non-negative Matrix Factorization Algorithm

With the booming development of science and technology, the whole human society has virtually been applied the information technology era, in which human have to face the challenge of efficient processing and analysis of large-scale information data. On this basis,it becomes very important to effectively analyze these huge data and extract valuable information. These huge data information usually exists in the form of matrix or tensor, in addition, as a new type of matrix decomposition method, the non-negative matrix factorization(NMF) has been successfully used in spectral data analysis, face recognition,data mining, cancer class discovery and other fields due to its advantages such as simple decomposition form, interpretable decomposition results, the small occupation of storage space.Focusing on the non-negative matrix factorization algorithm, this paper mainly proposed non-monotone projection alternating BB(Barzilai-Borwein) step-size algorithm and adaptive non-monotone BB(Barzilai-Borwein) step-size algorithm. Moreover this paper not only proved the convergence of two algorithms in theory and but also performed the program implementation of them, and found that the second algorithm(adaptive non-monotone BB(Barzilai-Borwein) step-size algorithm can be applied for face recognition. The main contents are as follows:First of all, the research background, the research significance, the basic knowledge of NMF and the classical algorithm of non-negative matrix factorization were briefly discussed, then the proposed algorithm was simply analyzed.Secondly, based on the framework of alternating non-negative least squares(ANLS), by combined with alternate BB step-size algorithm, Lipschitz constant gradient and non-monotone line search technique given by Grippo, Lamperiello and Lucidi, et.al, we proposed a non-monotone projected alternating BB step-size(NPABB) algorithm for non-negative matrix factorization, and theoretically proved that this algorithm was convergent. In addition, by comparing this algorithm with Ne NMF algorithm, projection alternating BB(APBB2) algorithm, quadratic regularization projected BB(QRPBB)method in terms of running time, the number of iterations, the relative error and gradient,the proposed algorithm was proved to be effective by the numerical experiments.Finally, based on the ANLS framework, a non-monotone adaptive BB step-size(NABB)algorithm for non-negative matrix factorization was proposed. Furthermore, due to the application of adaptive BB step-size and the gradient of the Lipschitz constant, the convergence rate of the proposed algorithm was accelerated, moreover since the step-size of the algorithm satisfies the non-monotone line search given by Zhang and Hager, the global convergence of the algorithm was guaranteed in theory. The numerical results showed that as compared with other algorithm, the new algorithm has significant advantages for processing the large-scale data problems and can obtain the smallest residual and gradient in the shortest possible period. Regarding the application in face recognition, the proposed algorithm was compared with the monotone projection BB(MPBB) algorithm in terms of reconstruction images and running time, finding that the new algorithm can achieve the same effect of reconstruction images in a shorter period of time.