Research On Greedy Reconstruction Algorithms For Compressed Sensing

Compressive sensing is a hot point in recent years. It breaks the limit of Shannon sampling theorem, and is used in many fields. Compressive sensing theory includes three parts: sparse representation, measurement design and reconstruction. In this paper we mainly discuss greedy reconstruction algorithms.Greedy reconstruction algorithms recovery the support of sparse signals(location of nonzero elements) iteratively, and then estimate the signal by Least Square Method. This kind of algorithms is simple in structure, easy to be implemented and has fast speed of reconstruction. This paper mainly deal with this kind of algorithms and the main work is as follows:First, a general framework of greedy reconstruction algorithms is summaried, and many existing algorithms, such as Orthogonal Matching Pursuit(OMP), Regularized Orthogonal Matching Pursuit(ROMP), Stagewise Orthogonal Matching Pursuit(StOMP), Subspace Pursuit(SP), Compressive Sampling Matching Pursuit(CoSaMP), Sparsity Adaptive Matching Pursuit(SAMP), Backtracking-Based Matching Pursuit(BAOMP), are introduced in detail. Some expirements are conducted in noiseless and noise cases to demonstrate their performances. It helps us have a deeper understand about greedy reconstruction algorithms.Second, Multipath Matching Pursuit(MMP) is researched. Unlike other algorithms, the MMP generates serveral candidate sets by multipath method. Then it selects the set with minimum residual as the final estimated support to improve reconstruction performance. By analyzing the MMP algorithm, the RIP conditions in noiseless and noise cases for ensuring exact reconstruction are given. Moreover, based on multipath idea and regularized strategy of ROMP, Regularized Multipath Subspace Pursuit(RMSP) algorithm is proposed. It divides the test set into several subsets in each iteration by means of regularization, and then selects one candidate with the minimal residual as the estimated support set in the iteration. The experiment result has shown that RMSP has a better performance than SP algorithm.Third, the influence of threthold on atom selection is analyzed. Based on Threshold Sparsity Adaptive Matching Pursuit(BT-SAMP) algorithm is proposed based on the atom selection strategy of BAOMP. It is an improvement of SAMP algorithm. Then By imitating SP embedded OMP algorithm, REASP Embedded OMP(ReEOMP) algorithm is proposed. It optimizes support of OMP in each iteration by REASP algorithm. The experiment result has shown that both BT-SAMP and ReEOMP have better performances when comparing with existing algorithms.