| Compressed Sensing is the recovery or reconstruction of a high-dimensional sparse data vector by means of a low-dimensional sampled data vector,in other words,solving the underdetermined matrix equation y＝Ax,where the dimension of the sampled data vector y is much smaller than that of the original vector x.In this thesis,we study the greedy algorithms for Compressed Sensing and obtain two main results.The first result is that we propose a variation of Hard Thresholding Pursuit(HTP)algorithm,called Truncatedly Graded Hard Thresholding Pursuit(TrGHTP).The numerical experiments show that the reconstruction probability of TrGHTP is significantly improved compared with the HTP algorithm when the original signals with different distributions are selected(especially in the case of non-negative signals),and the recovery time does not increase much.The reconstruction probability of TrGHTP algorithm is also higher than other greedy algorithms OMP(Orthogonal matching pursuit),IHT(Iterative hard thresholding),CoSaMP(Compressive sampling matching pursuit),NIHT(Normalized iterative hard thresholding),SP(Subspace pursuit).Applying the truncation idea to the above greedy algorithms,we get a series of truncated algorithms which have higher reconstruction probability than the original ones respectively except for Truncated OMP algorithm.The second result is that a staged greedy algorithm idea is proposed,in which the initial value is preprocessed by the TrGHTP algorithm first,and then the result is processed and used as the initial value of other greedy algorithms to continue the refinement.The numerical results show that each staged greedy algorithm performs better than the original algorithm respectively,and among them,HTP and SP algorithms have a more pronounced refinement effect.By rigorous mathematical analysis,we obtain that when the set Λ0 obtained from the preprocessing algorithm has at least p common elements with S,if the element xp of the original signal with the pth largest absolUte value satisfies |xp|≤ρ2s-p+2‖xS\Λ0*‖and the restricted isometry constant of the measurement matrix δ3s-p≤1/(?),then the TrGHTP-HTP algorithm can accurately reconstruct the original signal,where x*is the original signal,S is the support set of x*and s is the sparisity of x*. |
