Fast Correlation Method for Partial Fourier and Hadamard Sensing Matrices in Matching Pursuit Algorithms

There have been many matching pursuit algorithms (MPAs) which handle the sparse signal recovery problem, called compressed sensing (CS). In the MPAs, the correlation step makes a dominant computational complexity. In this paper, we propose a new fast correlation method for the MPA when we use partial Fourier sensing matrices and partial Hadamard sensing matrices which are widely used as the sensing matrix in CS. The proposed correlation method can be applied to almost all MPAs without causing any degradation of their recovery performance. Also, the proposed correlation method can reduce the computational complexity of the MPAs well even though there are restrictions depending on a used MPA and parameters.