Alternating Direction Method Of Multipliers To Solve K-means Clustering Problem

Non-negative Matrix Factorization(referred to as NMF)is a class of Matrix decomposition Method with non-negative constraints.This model is often used to process the text clustering,signal processing,pattern recognition,computer vision,and some practical problems in the field of image engineering.Due to the convexity of the model,the traditional algorithm is more difficult,even if can solve,its theoretical analysis may be more complex.Alternating Direction Method of Multipliers(referred to as ADMM)is an effective algorithm for solving the convex optimization problem,furthermore,the numerical experiments show that ADMM equally effective for solving some non convex optimization problems,and has some theoretical results.In this paper,we propose the ADMM in solving the text clustering model from a NMF.The sub-problem may not easy to solve,we use Gradient Projection method with self-adaptive step size rule to solve the sub-problems,resulted in more efficient calculation,and under certain assumptions algorithm convergence is analyzed,finally the effectiveness of the proposed method is verified by numerical experiments.For the Non-negative Matrix Factorization we studied,(?)Because there is no non-convex orthogonal constraint,it is relatively easy to solve the non-negative matrix decomposition model.In recent years,some scholars have done a lot of research on the decomposition of orthogonal non-negative matrices,but the convergence can only be obtained under relatively strict assumptions,and for general non-convex problems,only under certain assumptions can the convergence be better verified.Therefore,in this paper,we only study the non-negative matrix decomposition model without orthogonal constraint.Experimental results show that that the clustering performance of ADMM for solving the model is superior to that of K-means algorithm under most problem Settings.