The Algorithm Research For Matrix Completion

Matrix completion is to reconstruct the low rank or approximation low rank matrix from the lim-ited information,which is one of hot topics in the field of signal processing in recent years.However,the sampling matrix is either common matrix or special matrix which has structure such as Hankel and Toeplitz.Meanwhile,Toeplitz matrix play an important role in signal and image processing.Therefore,in this paper,we study matrix completion for Toeplitz matrix and common matrix in more detail.We discover that most of the existing algorithms are required to compute the singular value decomposition of matrix through the research and summary of matrix completion,and it is time-consuming to compute the singular value decomposition through numerical experiments.For the completion of the Toeplitz matrix,according to the algorithm complexity of the singular value de-composition is O(n3)for the common matrix and it is O(n2logn)for Toeplitz matrix,and by the least squares approximation to the known entries in the left singular vector space,this algorithm forms a new feasible matrix,and the matrices generated by iteration keep Toeplitz structure by making use of averaging the diagonal entries.So that,the new algorithm reduces the time of decomposition in the singular vector space.For the completion of the common matrix,a two-stage iteration algorithm is proposed based on the steepest descent method.The inner iteration finds the matrix which is up to the shortest or approximation shortest distance and the outer iteration finds the optimal r-dimensional manifold with two kinds criterion.In theory,we prove the convergence of two new algorithms under some conditions.Through numerical experiment,we verify reasonability and superiority of two new algorithms.By comparing the experimental results,we can find the new algorithm reduces the CPU time that will be benefit to solve large-scale common matrix and Toeplitz matrix completion problem.Furthermore,it can be time saving and cost reducing in practical application.