An improved complementary matching pursuit algorithm for compressed sensing signal reconstruction

The complementary matching pursuit (CMP) algorithm is analogous to the classical matching pursuit (MP), but performs the complementary action. It deletes (N-1) atoms from the sparse approximation at each iteration and keeps only one atom while other algorithms select one atom and add it into the sparse approximation, which makes CMP have better reconstruction quality. However, remaining only one atom at each iteration costs more time in CMP. In this work, an improved CMP algorithm is proposed to shorten the reconstruction time. The proposed CMP algorithm selects more than one atoms at each iteration following a certain rule from Sparsity Adaptive Matching Pursuit(SAMP). In which, the number of selected atoms changes with Adaptive Size (AS) every iteration. The experiment results show that the improved method could achieve better reconstruction quality with less time than the Gradient Pursuit (GP), Orthogonal Matching Pursuit (OMP) and original CMP.