Methods For Solving Symmetric Nonnegative Matrix Factorization

Symmetric nonnegative matrix factorization(SymNMF)is a powerful tool for data dimensionality reduction and has found many applications in pattern recognition,data mining,etc.The objective function of SymNMF problem is nonconvex quartic polynomial,so it is difficult to find the global minimum.Based on the structure and optimality conditions of SymNMF model,we transform the SymNMF problem into two easily solvable equivalent problems and propose different methods to solve corresponding equivalent problems.Firstly,SymNMF model is treated as a general nonlinear programming problem by separating symmetric variables.We propose an approximate augmented Lagrangian method to solve the problem by introducing an auxiliary variable,and discuss the effective solution of the augmented Lagrangian subproblem.It can be proved that the limit point generated by the proposed method is the stationary point of SymNMF under certain conditions.The augmented Lagrangian subproblem is solved by the proximal alternating minimization method and the sequences generated by this method converge to the stationary point of the augmented Lagrangian subproblem.Secondly,this paper proposes a bounded SymNMF model by analyzing the optimality conditions of the SymNMF model.The one-to-one correspondence between the Karush-Kuhn-Tucker(KKT)points of the bounded model and the KKT points of the SymNMF model can be proved.An proximal gradient method for solving bounded SymNMF model is constructed based on average curvature and backtracking technique,which is named as average curvature proximal gradient method.For this method,we give convergence analysis under backtracking technique and iterative complexity analysis under subgradient minimum norm.Numerical experiments based on synthetic data and real data show that the approximate augmented Lagrangian method and average curvature proximal gradient method proposed in this paper have obvious advantages in running time and clustering accuracy compared with existing methods for SymNMF problem.