Research On Efficient Optimization Algorithms And Theory For Solving Nonnegative Matrix Factorization Problems

With the rapid development of computer and information technology,obtaining latent low-dimensional representations for raw high-dimensional data is necessary and challenging.Nonnegative matrix factorization(NMF),as a popular tool for dimensionality reduction and feature mining,has been widely applied into big data mining and machine learning.In order to improve the computational efficiency and quality of factorizing large-scale data matrices,this thesis focuses on the optimization techniques applicable for solving complex large-scale NMF problems and designs some efficient algorithms.A new adaptive Barzilai-Borwein(BB)step size is proposed by integrating advantages of two classical BB step sizes.Combined with the steepest descent direction,a simple gradient descent algorithm is designed for solving large-scale optimization problems.Then global and local linear convergence analysis of the algorithm are conducted.Actually,the proposed BB step size can provide an approximate Hessian matrix for the objective function.As for large-scale problems of NMF,a new alternating nonmonotone projected BB algorithm is developed.Unlike existing algorithms in the literature,the developed algorithm combines a nonmonotone line search technique with a spectral gradient projection strategy to find suitable step sizes,and employs the new adaptive BB step size to generate search directions.Apart from establishment of global convergence of this algorithm,extensive numerical tests on synthetic datasets and real-world datasets are conducted.It is concluded that our algorithm is promising and applicable to face image reconstruction,and deep mining of transcriptomic profiles of the sub-genomes in hybrid fish lineage,compared with the state-of-the-art algorithms,in terms of numerical efficiency,noise robustness and factorization quality.Aimed at efficient solution of generalized NMF problems with single factor matrix variables,a new nonmonotone line search rule is proposed by extending the well-known ones and inheriting their advantages.Then,by analyzing and employing nice properties of this rule,a new nonmonotone spectral projected gradient algorithm is developed to solve box-constrained optimization problems in matrix space and global convergence of the developed algorithm is established.Numerical tests further show the proposed rule can significantly accelerate convergence of algorithms by reducing the number of function evaluations and iterations.To overcome drawbacks of the popular multiplicative update(MU)algorithms in solving generalized NMF problems,a new block coordinate descent algorithm is developed on the basis of the proposed line search technique,and its global convergence is established.Particularly,this algorithm adopts the proposed nonmonotone spectral projected gradient algorithm to alternatively solve the NMF subproblems with single factor matrix variables to generate an approximate solution sequence.Numerical results on three public image datasets show that our algorithm generates more accurate and robust clustering results and solves an orthogonal dual graph regularized NMF model with smaller reconstruction errors and higher orthogonality,compared with MU.Unlike methods based on the block coordinate descent framework,another new algorithm is developed for the generalized NMF problems,called the nonmonotone gradient descent algorithm.This algorithm has no inner loops,but updates both factor matrices simultaneously at each iteration by using appropriate step sizes and good search directions.After establishment of global convergence,numerical tests on public image datasets show the superiority of the developed algorithm in terms of clustering performance,noise robustness,computational efficiency and quality of results.Based on a new strategy,an extended nonmonotone line search technique is proposed.In contrast to existing methods,this technique can flexibly control the nonmonotonicity of the line search so as to enhance the numerical efficiency of algorithms.Combined with a sufficiently descent direction,a new algorithm is developed to solve large-scale box-constrained optimization problems of NMF.Global convergence of the developed algorithm is established.And the numerical superiority of this technique is verified.Motivated by advantages of the prox-linear approximation,new nonmonotone line search techniques and the adaptive BB step size,two accelerated nonmonotone projected BB algorithms are developed for solving NMF problems which optimize one factor matrix with another fixed.Based on the block coordinate descent framework,two efficient NMF algorithms are introduced,and the corresponding global convergence is established.Numerical tests on synthetic and real-world datasets verify the superiority of the proposed algorithms in terms of convergence speed,matrix reconstruction quality and noise robustness.