Sparsity and Step-size adaptive regularized matching pursuit algorithm for compressed sensing

A novel greedy matching pursuit reconstruction algorithm for compressed sensing (CS) was proposed in this paper, called Sparsity and Step-size Adaptive Regularized Matching Pursuit (SSARMP). Compared with other traditional matching pursuit algorithms, e.g. Orthogonal Matching Pursuit (OMP), SSARMP can recover the sparse signal without prior information of the sparsity, and compared with Sparsity Adaptive Matching Pursuit (SAMP) algorithm, the presented algorithm can get a compressibility estimation by estimating the signal's compressibility firstly and then set this estimation value as the finalist in the first stage. The regularized idea and the variable step-size were added in selecting elements of the candidate set and changing finalist stage respectively. A reliable numerical sparsity estimation can reduce the number of iterations of the algorithm and the regularized and variable step-size can improve the recovery accuracy obviously. So, SSARMP can finally reach better complexity and better reconstruction accuracy at the same time. Simulation results show that SSARMP outperforms almost all existing iterative algorithms without prior information of the sparsity, especially for compressible Gaussian signal.