Nonnegative Matrix Factorization And Its Applications

With the rapid development of the information technology,a large number of highdimensional data have been generated.Some traditional methods for dimensionality reduction,such as principal component analysis(PCA)and singular value decomposition(SVD),can produce negative values.However,in some practical application scenarios,negative values are meaningless.Nonnegative matrix factorization(NMF)was first proposed by Lee and Seung [1] in 1999.It has been widely applied in many fields,such as image processing [1],text clustering [2] and community discovery [3].Comparing with other matrix factorization methods,it has great interpretability due to its nonnegativity of elements.For example,negative pixel values are meaningless in image processing.In text clustering,the positive value represents that the document belongs to a topic with a certain probability,while the negative values have no practical significance.For the theoretical research of NMF,there are mainly two aspects: one is the algorithms for NMF,and the other is the initialization for NMF.There are many algorithms to compute the NMF,which can be roughly divided into three categories: Multiplicative Update Rules(MU),Projected Gradient Methods and Alternating Nonnegative Least Squares(ANLS).For the research of the initialization algorithms for NMF,there are also many methods which can be divided into two categories in general.The most commonly used initialization algorithms are based on SVD.The representative ones are the SVD-NMF [6] proposed by Qiao and the NNDSVD [5] proposed by Boutsidis et al.As for the application of NMF,it is focused on clustering and image processing.What's more,we introduce the relationship between symmetric NMF and clustering as well as the asymmetric NMF and clustering.We also indroduce the specific principles of NMF in face reconstruction and face recognition.Frieze et al.[22] proposed a Monte Carlo algorithm for finding low-rank approximations.This method can save computation time greatly.This idea is used for solving the least squares problem by Chia [23].Considering that the existing initialization methods based on SVD usually focus on the original matrix,when the dimension of the matrix is very large,it is time-consuming to use SVD algorithm on the original matrix directly.Enlightened by the idea of Frieze et al,we propose an initialization algorithm based on Monte Carlo method(FKV-NMF).We construct a much smaller matrix by sampling and compute the SVD of this small matrix.Then W and H can be initialized in less time.Through numerical experiments,we demonstrate that our initialization algorithm needs less time and the accuracy is also maintained to some extent.