From Denoising to Compressed Sensing

Abstract--A denoising algorithm seeks to remove noise, errors, or perturbations from a signal. Extensive research has been devoted to this arena over the last several decades, and as a result, todays denoisers can effectively remove large amounts of additive white Gaussian noise. A compressed sensing (CS) reconstruction algorithm seeks to recover a structured signal acquired using 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 an extension of the approximate message passing (AMP) framework, called Denoising-based AMP (DAMP), that can integrate a wide class of denoisers within its iterations. We demonstrate that, when used with a high performance denoiser for natural images, DAMP offers state-of-the-art CS recovery performance while operating tens of times faster than competing methods. We explain the exceptional performance of DAMP by analyzing some of its theoretical features. A key element in DAMP is the use of an appropriate Onsager correction term in its 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. The fundamental challenge faced by a compressed sensing (CS) reconstruction algorithm is to reconstruct a highdimensional signal from a small number of measurements. In a single pixel camera, Φ might be a sequence of 1s and 0s representing the modulation of a micromirror array [3]. " Ψu with sparse u, where Ψ represents the inverse transform matrix. C. Metzler and R. Baraniuk are with the Department of Electrical and Computer Engineering, Rice University, Houston, TX 77023 USA (email: chris.metzler@rice.edu and richb@rice.edu). A. Maleki is with the Department of Statistics, Columbia University, New York, NY 10023 USA (email: arian@stat.columbia.edu). The work of C. Metzler supported by the NSF GRF Program and the DoD NDSEG Program. The work of A. Maleki was supported by the grant NSF CCF-1420328. However, when dealing with large signals, such as images, these convex programs are extremely computationally demanding. Therefore, lower cost iterative algorithms were developed; including matching pursuit [6], orthogonal matching pursuit [7], iterative hard-thresholding [8], compressive sampling matching pursuit [9], approximate message passing [10], and iterative soft-thresholding [11]-[16], to name just a few. See [17], [18] for a complete set of references. Here, δ " m{n is a measure of the under-determinacy of the problem, x y denotes the average of a vector, and The role of this term is illustrated in Figure 1. A QQplot is a visual inspection tool for checking the Gaussianity of the data. In a QQplot, deviation from a straight line is an evidence of non-Gaussianity.