A new compressed sensing-based matching pursuit algorithm for image reconstruction

Compressed Sensing (CS), a popular technique which seeks to capture a discrete signal with a small number of linear measurements, could be used to compress a signal during the process of sampling. As an iterative greedy reconstruction algorithm for practical CS, sparsity adaptive matching pursuit (SAMP) takes advantage of the capability of signal reconstruction without prior information of the sparsity in the process of resuming the original high-dimension-data from low-dimension measurement. This paper presents a backward and adaptive matching pursuit reconstruction algorithm with fixed step sizes to avoid the overestimation phenomena of SAMP by using a standard regularized approach. Firstly, a fixed and biggish step size is set to make sure the size of support set of the signal to be reconstructed increasing stably. The energy difference between adjacent reconstructed signals is then taken as the halting condition of iteration. A standard regularized approach is employed to post-dispose the final iteration results, which backward eliminates superfluous atoms to acquire exact reconstruction. Experimental results show that such an improvement of SAMP is feasible in technology and effective in acquiring quick and exact reconstruction with sufficient measurement.

I. Introduction

As a fundamental result in the field of information theory, the well-known Nyquist-Shannon sampling theorem that the sampling rate must be at least twice the maximum frequency of the signal is taken as a golden rule in the area of signal processing. However, the theorem seems not considering the intrinsic structure of the sampled signal during the sampling. Compressed sensing (CS) theory recently presented by Donoho et al in [1]–[3] shows that sparse or compressive signals can be well coded by a small number of incoherent and random projections of them. Thus those signals could be reconstructed by some certain types of nonlinear decoding mechanisms. Because CS does not adopt the sampling rate of Nyquist but the small number of random projection, compared to the dimension of the signal, a direct advantage is that the sparsity limited to the signal enables the signal to be reconstructed from the small number of projections. In the CS research, one challenge is to develop a quick reconstruction algorithm with reliable accuracy.