BM3D-AMP: A new image recovery algorithm based on BM3D denoising

A denoising algorithm seeks to remove perturbations or errors from a signal. The last three decades have seen extensive research devoted to this arena, and as a result, today´s denoisers are highly optimized algorithms that effectively remove large amounts of additive white Gaussian noise. A compressive sensing (CS) reconstruction algorithm seeks to recover a structured signal acquired from a small number of randomized measurements. Typical CS reconstruction algorithms can be cast as iteratively estimating a signal from a perturbed observation. This paper answers a natural question: How can one effectively employ a generic denoiser in a CS reconstruction algorithm? In response, we develop a denoising-based approximate message passing (D-AMP) algorithm that is capable of high-performance reconstruction. We demonstrate using the high performance BM3D denoiser that D-AMP offers state-of-the-art CS recovery performance for natural images (on average 9dB better than sparsity-based algorithms), while operating tens of times faster than the only competitive method. A critical insight in our approach is the use of an appropriate Onsager correction term in the D-AMP iterations, which coerces the signal perturbation at each iteration to be very close to the white Gaussian noise that denoisers are typically designed to remove. On the analytical side, we develop a new state evolution framework for deterministic signals that accurately predicts the performance of D-AMP and enables us to derive several useful theoretical features.