Research On Accelerated ADM Algorithm For Large-Scale Matrix Completion Problems

With the rapid development of computer technology,big data and artificial intelligence have become one of the hot topics in society.In these areas,people need to analyze and process large-scale data.However,in the process of processing,storage and transmission,these data often suffer from problems such as loss,damage and noise pollution.Matrix completion techniques are very effective in solving the problems of matrix data loss,damage and noise pollution,and has become one of the hot topics in computer vision,artificial intelligence,optimization and many other research fields in recent years.The matrix completion problem refers to how to complete other unknown elements of a matrix reasonably and accurately from the known elements of a low-rank or approximately low-rank matrix.At present,many researchers have studied the matrix completion problem in terms of theory and algorithm design.However,with the geometric growth of massive data,the efficiency of the existing algorithms is not very high when the matrix is large.Therefore,designing fast and effective algorithms for solving large matrix completion problems has become one of the hot topics in the field of scientific computing.The alternating direction method is attractive for solving matrix completion problems,since it has the advantage of being able to decompose a minimization problem into many smaller and easier subproblems.Therefore,this thesis focuses on alternating direction method,we propose two effective algorithms,and the convergence of the new algorithms are analyzed and the numerical experiments.The main works of this paper are as follows:First,in this thesis,we propose an inertial accelerated alternating direction method for solving the large-scale matrix completion problem using the framework of alternating direction method and inertial strategy.In each iteration of the new method,for some of variables,the iterative points of the previous two iterations of the alternating direction method are extrapolated to obtain the new iteration points,which improve the computational efficiency of the new method.Under reasonable assumptions,the convergence of the new algorithm is proved.Finally,the numerical experimental results of the random matrix completion and image restoration examples show that the new algorithm has advantages in terms of computation time and number of iterations compared with the original alternating direction method.Second,in order to further improve the efficiency of alternating directions,based on the first work,we obtain the new inertial iteration point by linear combination of the previous iteration point and the previous inertial iteration point of the subproblem.Thus we propose an improved inertial alternating direction method for the large-scale matrix completion problems in this thesis.Under reasonable assumptions,the convergence of the new algorithm is proved.Finally,the numerical experimental results of random matrix filling and image restoration examples show that the new algorithm has more obvious advantages in terms of computation time and number of iterations.