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

Kee-Hoon KIM  Hosung PARK  Seokbeom HONG  Jong-Seon NO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.8   pp.1674-1679
Publication Date: 2014/08/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1674
Type of Manuscript: PAPER
Category: Digital Signal Processing
compressed sensing,  Fourier,  Hadamard,  low-complexity,  matching pursuit,  sensing matrix,  

Full Text: PDF(1.1MB)>>
Buy this Article

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.