Study On The Improvement Of Augmented Lagrange Multiplier Algorithm For Toeplitz Matrix Completion

With the development of computer technology rapidly,big data and artificial intelligence have become one of the mainstream topics in the society,and the large-scale matrix data analysis and processing are often encountered in these fields.However,we often encounter the data loss,blur and other problems in the processing of matrix data,so as to need the matrix reconstruction.Matrix completion is one of the most effective methods to solve the problem of matrix data loss.It has been applied widely in the field of information science such as machine learning,digital image processing,meteorological forecast,video denoising,pattern recognition,computer vision and so on.It is also one of the hot research spots in recent years.Matrix completion is to recover the missing data via using part of the known data informa-tion in the original matrix,so as to construct a low-rank matrix to approximate the original matrix.At present,both theoretical research and algorithm design have made relatively abundant scientific achievements for the general matrix completion problem.However,for the Toeplitz matrix of wide application in practice and having a special structure,the research of the completion problem has not perfect enough.Therefore,in terms of the Toeplitz matrix completion problem,this paper studies the improvement of the famous augmented Lagrange multiplier algorithm,designs mainly several fast algorithms,and presents the convergence analysis and numerical experiments of the new algorithms.The basic structure of this paper is outlined as follows:In Chapter 1,the research background and basic principle of matrix completion are described.The corresponding mathematical model of matrix completion problem and three kinds of algorithms associated with this paper to solve the problem are introduced emphatically.And we give the segmen-tal definitions and lemmas involved in this paper.Meanwhile,the related content of Toeplitz matrix is given.Finally,the main work of this paper is illustrated briefly.In Chapter 2,based on the special structure and properties of Toeplitz matrix,we propose struc-tured augmented Lagrange multiplier(SALM)algorithm step by step for the Toeplitz matrix comple-tion by introducing structured operator.The main idea of the algorithm is to structure the iterative matrix at each step,namely to reassign the diagonal elements of the matrix via the operator to take shape the Toeplitz structured matrix.In this way,the approximation matrix always maintains the Toeplitz structure in the iteration process,so that the fast singular value decomposition of Toeplitz matrix can be utilized to economize the time.The convergence theory of the new algorithm is further discussed.Finally,numerical experiments show that SALM algorithm is more effective than accel-erated proximal gradient(APG)algorithm and augmented Lagrange multiplier(ALM)algorithm in terms of the iterative steps,computation time and repairing effect.In Chapter 3,based on the SALM algorithm and modified augmented Lagrange multiplier(MALM)algorithm,two kinds of multi-step structured augmented Lagrange multiplier(l-SALM and l-MALM)algorithms for Toeplitz matrix completion are proposed.The main idea of the two kinds of algorithms is to use the structural operator and mean calculation once per l-step,which reduces the necessary massive data transmission in the process of transforming into Toeplitz matrix every step in SALM and MALM algorithms.In this way,on the one hand,the fast algorithm can be used to save the time of singular value decomposition after the structural completion matrix to Toeplitz.On the other hand,the data transmission cost of the structured process can be partly saved.Finally,numerical experiments make clear that compared with SALM and MALM algorithms,l-SALM algorithm and l-MALM algorithm can not only save computation time but also improve the accuracy of matrix completion.Doing both is more effective.In Chapter 4,we summarize the whole paper,and put forward the following assumptions:we mainly consider Toeplitz matrix completion problem in this paper.Moreover,the high-dimensional data is also flooding the every field in the practical application,and the tensor data has been com-mon,so we intend to extend the work of this paper to the high-dimensional tensor recovery problem.Specifically,the structured idea will be further extended to the tensor completion problem with special structure,so that the effective algorithms for solving the structured tensor completion problem is de-rived.We also consider applying structured idea to solving the large-scale system of linear equations,optimization and other application problems.