CSMP: Compressive Sensing Matching Pursuit Based on Restricted Isometry Property

Compressive sensing consists of compressed sampling and sparse reconstruction, which is a method to compute sparse solution for underdetermined linear systems. Large scale and fast reconstruction method has become an active research topic of compressive sensing. In this paper, a matching pursuit algorithm is presented and named CSMP. It adopts iterative framework and best s term approximation to update signal support and magnitude. Convergence analysis is developed based on restricted isometry properties (RIP). The sufficient condition for the convergence of CSMP is established with 3s order restricted isometry constant (RIC) less than 0.23, which relaxes the RIC condition for recovering s sparse signal by matching pursuit and improves the convergence speed. In order to adapt for large scale sparse signal reconstruction, the proposed method is equipped with matrix-vector multiplication operator which can select subsets of both random projection measurements and sparse bases, therefore becoming able to utilize discrete cosine transform and wavelet transform, avoiding explicit storage of large scale matrix. Compressive sampling and reconstruction experiments are conducted on 2\+{20} sparse Gaussian signal with random support and on 512 by 512 Lenna image. Comparisons with other algorithms demonstrate that the proposed method is stable and fast for large scale sparse signal reconstruction in compressive sensing.