Lanczos Bidiagonalization Based Initialization: A Fast Head Start For Nonnegative Matrix Factorization

In 1999,"Nature" published a paper showing an outstanding result in the research of non-negative matrix of mathematics,written by Professor Lee and Professor Seung.In this paper,the authors present a new method of matrix decomposition,named non-negative matrix factorization(NMF) algorithm, a method applied on the condition that all the elements in the matrix are non-negative.Because of the broad application of non-negative matrix factorization in real life,the publication of this paper caught the eyes of a number of researchers studying in some specific field for the following reasons:On the one hand,many large-scale data analysis in scientific research needs to be processed effectively in the form of matrixes,and NMF can provide a new way for human in processing the large-scale data;On the other hand,compared with some of other traditional algorithms,NMF decomposition algorithm shows a number of advantages,such as the simplicity in realization,easily explainable toward the form of and the result of decomposition,as well as less storage space.In[2],C.Boutsidisa and E.Gallopoulos proposed a SVD based initialization algorithm designed to enhance the initialization stage of nonnegativc matrix factorization.Combined with other NMF algorithms,it can accelerate convergenece rate rapidlly.For a large nonnegativc matrix,a Lanczos bidiago nalization process is utilized to obtain a nonnegativc bidiagonal matrix of low rank,and then every unit rank matrix produced from the Lanczos process is approximated by its nonncgative section in the same way as developed in[2]. This results in a noval initialization algorithm for vomiegative matrix factorization (NMF).It can readily be combined with existing NMF algorithms and may contain a little randomization.Some numerical experiments demonstrate that the new initialization algorithm is more efficient than the SVD based initialization algorithm presented in[2].Five sections are folded in this thesis.Section 1 give us the introduction of NMF and the initializaiton of NMF and looks back the former works of this area.In section2,we review the Lanczos bidiagonalization process to get a low-rank approximation.In sectin3,we present a strategy to get nonnegative approximation matrices W and H from the Lanczos bidiagonalization process. In section4,we give some experiments to compare our method with C.Boutsidis and E.Gallopoulous' method and demonstrate the advantages of our methods. In section 5,we give a conclusion of our thesis.