Performance bounds of compressed sensing recovery algorithms for sparse noisy signals

Recently, the performance bounds of the compressed sensing (CS) recovery algorithms have been investigated in the noisy setting. However, most of the papers only focus on the noisy measurement model where the signal is noiseless and the noise enters after the CS operation. The noisy signal model where both the signal and the compressed measurements are contaminated by the different noises is not considered. This paper works on the noisy signal model and provides the performance bounds for the following popular recovery algorithms: thresholding and orthogonal matching pursuit (OMP), Dantzig selector (DS) and basis pursuit denoising (BPDN). The performance of the recovery algorithms is quantified as the ℓ2 distance between the reconstructed signal and the true noisy signal. Next, the impacts of the noise are analyzed on the basis of the quantified performance. The analysis results show that the effective way to restrain the impact of the noise is to choose the measurement matrix with low correlation between the columns or the rows. Finally, the theoretical bounds are verified with numerical simulations by calculating the mean-squared-error for the different noise variances. The simulation results show that OMP owns the better performance than the other three recovery algorithms under the noisy signal model.