Study Of Sparse Recovery Algorithms And Their Comparison

Convex optimization algorithms have demonstrated their effectiveness for solving convex compressive sensing problems.And they are widely used in signal and image processing.However,their sparsity promoting ability is not as good as that of non-convex compressed sensing algorithms.Non-convex compressive sensing problem generally has a strong property that the problem considered is non-convex,non-smooth,non-Lipschitz continuous.Thus it cannot be solved fast and effectively.In this thesis,modified greedy algorithms,including Gradient Pursuit,Hard Thresholding Pursuit and Graded Hard Thresholding Pursuit,and Iterative ₁l Minimization Framework for tackling non-convex compressive sensing problems are considered respectively.Based on Hard Thresholding Pursuit and Matrix Pseudoinverse,the^?A Graded Hard Thresholding Pursuit was proposed for compressive sample problems.For the recovery of sparse vectors,the required number of iterations of this method is exactly equal to the sparse level.Using the idea from Generalized Orthogonal Matching Pursuit and introducing the capture cardinality of support set,Matrix Pseudoinverse Hard Thresholding Pursuit was proposed to reduce the iteration number and running time.Simultaneously,^?A Graded Hard Thresholding Pursuit is a particular sample of Matrix Pseudoinverse Hard Thresholding Pursuit,i.e.whenN₀?28?1,Matrix Pseudoinverse Hard Thresholding Pursuit is extended toA^?Graded Hard Thresholding Pursuit.Theoretical results and numerical examples show,that without changing the requirement of storage and the complexity of algorithm implementation,modified greedy algorithms have better performance than the original version in terms of recovery rate,average iteration number and running time.As for Iterative ₁l Minimization Framework,it performs consistently stable to the conditioning of sensing matrix,and also outperforms Basis Pursuit regardless of the conditioning of sensing matrix.