Research On The Thresholding Algorithm And Match Pursuit Algorithm For Compressed Sensing And Matrix Completion

Compressed sensing and matrix completion are two theories of signal acquisition and processing.Both of them deal with two different problems,however they have close connection with each other.l0 norm minimization problem is the major problem of com-pressed sensing.Its purpose is to find the most sparse solution in the infinite solution of the underdetermined equations to construct the original signal(vector).The purpose of matrix completion is to construct a low rank matrix to approximate the original matrix by some given elements of the original matrix.The design of the algorithms for solving these two reconstruction problems is always the focus of compressed sensing and matrix completion.In this dissertation,we will study the reconstruction algorithm of com-pressed sensing and matrix completion.Main work and innovation can be generalized as follows.(1).This dissertation first analyzes reconstruction algorithm of compressed sens-ing:Iterative Soft Thresholding algorithm,Iterative Hard Thresholding algorithm,Iter-ative Firm Thresholding algorithm and the Quasi-Soft Thresholding algorithm.Then,the parametrization of the quasi-soft threshold operator are updated to obtain the varied parametric quasi-soft threshold algorithm in every iteration.The convergence of the al-gorithm is proved.And the numerical results show that the varied parametric quasi-soft threshold algorithm can effectively improve the accuracy of signal reconstruction.(2).Based on orthogonal matching pursuit and multi-candidate orthogonal match-ing pursuit algorithms,in this dissertation,we propose a varied-candidate orthogonal matching pursuit algorithm for compressed sensing.The iterative principle and iterative scheme are given.Numerical experiments by one dimensional simulation show that the new algorithm can improve the accuracy of signal restoration and reconstruction proba-bility.(3).Based on the analysis of Iterative Soft Thresholding algorithm,Iterative Hard Thresholding algorithm and the Quasi-Soft Thresholding algorithm,the dissertation pro-poses parameterized quasi-soft thresholding algorithm and varied parametric quasi-soft thresholding algorithm of matrix completion.The convergence of these algorithms is proved.Numerical experiments show that the Quasi-Soft Thresholding algorithm and varied parametric quasi-soft thresholding algorithm improve the accuracy of matrix com-pletion.(4).This dissertation analyzes the orthogonal rank-one matrix pursuit algorithm of the matrix completion problem,and then the algorithm is extended to the low rank approximation pursuit algorithm.Differing from the orthogonal rank-one matrix pursuit algorithm,the low rank approximation pursuit algorithm selects multi-candidates and adds them to the basis set in each iteration step.It is the procedure of selecting multi-candidates with the orthogonal rank-one matrix pursuit algorithm and further decreasing the computational complexity.It is proved that the new algorithm is linearly conver-gent.Finally,numerical experiments show that the new algorithm is effective for image restoration and recommendation system,and it has less computation time.