PaperlayerView exact revision on arXiv

Source-linked AI summary

From Denoising to Compressed Sensing

Christopher A. Metzler, Arian Maleki, Richard G. Baraniuk

arXiv:1406.4175v5cs.ITmath.STstat.ML

TL;DR

The paper asks how generic denoisers can be used effectively for compressed sensing, especially when signals contain structures beyond sparsity. It develops D-AMP, an AMP extension with denoisers and an Onsager correction, and reports strong recovery, accurate state-evolution predictions, and robustness to measurement noise. The theory is restricted to Gaussian or subGaussian measurement matrices and relies on residuals being Gaussian.

  • Problem

    The paper addresses how to recover structured signals with generic denoisers when existing denoisers may not capture all structures in a signal class.

  • Method

    D-AMP treats denoisers as black-box components within AMP and uses an Onsager correction together with deterministic state evolution to analyze performance.

  • Results

    D-AMP delivers state-of-the-art compressively sampled image recovery, accurately predicted MSE in tested high-dimensional settings, and exceptional robustness to measurement noise, outperforming other methods by up to 7.4 dB in some tests.

  • Takeaways & Limitations

    A denoiser matched to the signal model can be plugged into AMP to recover compressively sampled signals across different signal classes.

  • Takeaways & Limitations

    The theory relies on Gaussian residuals and has been established for i.i.d. Gaussian or subGaussian measurement matrices, leaving theoretical validation and Fourier-sample extensions open.

Abstract

from arXiv · show

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, today's 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 (D-AMP), that can integrate a wide class of denoisers within its iterations. We demonstrate that, when used with a high performance denoiser for natural images, D-AMP offers state-of-the-art CS recovery performance while operating tens of times faster than competing methods. We explain the exceptional performance of D-AMP by analyzing some of its theoretical features. A key element in D-AMP 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.

I. INTRODUCTION

The paper addresses compressed sensing of non-sparse signals by embedding generic denoisers within AMP, using the Onsager correction to make effective noise approximately Gaussian. D-AMP supports diverse signal classes, strong image recovery, and state-evolution-based analysis.

  • A. Compressed sensing: Compressed sensing reconstructs high-dimensional signals from fewer measurements, requiring structural assumptions because the inverse problem is severely under-determined.Sparse recovery can use BPDN and iterative thresholding, but large-scale convex optimization is computationally demanding.
  • A. Compressed sensing: The Onsager correction makes AMP’s effective noise approximately Gaussian, unlike the heavy-tailed effective noise observed for IST.This Gaussianity supports algorithm analysis, parameter tuning, and convergence, and lets D-AMP use denoisers designed for Gaussian noise.
  • B. Main contributions: Natural images are often not exactly sparse in standard transform bases, limiting sparsity-based recovery methods.Barbara’s wavelet coefficients are predominantly non-zero, motivating recovery methods that capture richer image structure.
  • B. Main contributions: D-AMP extends AMP by treating a denoiser as a black box that maps a signal plus Gaussian noise to an estimate.This design allows denoisers based on simple or complicated structures to be applied across signal classes without specifying their internal models.
  • B. Main contributions: D-AMP combines broad applicability, strong recovery performance, robustness to measurement noise, and an analysis framework based on state evolution.The proposed state evolution predicts D-AMP’s MSE accurately in the tested high-dimensional settings and connects measurement requirements to denoiser performance.
  • B. Main contributions: NLM-AMP substantially outperforms wavelet-based AMP on a piecewise constant signal because it uses a more effective denoiser for that signal type.The comparison illustrates how replacing the denoiser can improve AMP recovery without requiring the same sparsity model.

2) Model-based CS imaging:

D-AMP leverages generic denoisers for compressed sensing by combining denoising with approximate message passing and an Onsager correction. This produces approximately Gaussian effective noise, supporting accurate analysis and improved recovery for non-sparse signals.

  • Advantages and analysis: D-AMP’s framework supports broad denoiser applicability, robustness to measurement noise, and analysis of recovery behavior and limitations.The paper also reports that NLM-AMP dramatically outperforms original AMP when NLM better matches piecewise-constant signals than wavelet thresholding.
  • D-AMP mechanism: The Onsager correction distinguishes D-AMP from D-IT and is used to make the effective noise resemble independent Gaussian noise at each iteration.Empirical evidence includes a highly Gaussian D-AMP noise distribution and non-Gaussian deviations for D-IT.
  • Denoiser properties: Soft-thresholding becomes effective for sparse signals, with its optimized threshold level depending on normalized sparsity.The denoiser properties section also introduces near proper denoisers for cases involving noise-independent error or bias.

C. State evolution

D-AMP uses a deterministic state-evolution framework to predict intermediate mean squared error across iterations. Simulations show accurate predictions for D-AMP, unlike D-IT, under the studied conditions.

  • State-evolution framework: State evolution generates equations that predict D-AMP’s intermediate MSE at each iteration.The framework begins from an initial error parameter and recursively produces the predicted sequence.
  • D-AMP prediction: D-AMP’s empirical MSE is accurately predicted by state evolution for large-dimensional problems under the paper’s stated initialization and assumptions.The formal finding assumes x0 = 0 and large m and n.
  • Empirical comparison: BM3D-AMP follows its state-evolution prediction, whereas BM3D-IT does not.The comparison is shown using MSE versus iteration count and is attributed to the differing effective-noise behavior.
  • Empirical validation: The reported validation covers BM3D, BLS-GSM, non-local means, and AMP with soft-wavelet-thresholding denoisers.The paper states that simulations checked the finding across these denoising algorithms.

D. Analysis of D-AMP in the absence of measurement noise

In the noiseless setting, the paper analyzes D-AMP’s success and failure through state evolution and relates recovery to measurement density and denoiser properties. Proper denoisers can yield exact recovery above a threshold, while near proper denoisers generally admit only an error bound.

  • Analytical assumptions: The analysis requires denoiser regularity such as Lipschitz continuity, though advanced image denoisers tested empirically followed the state-evolution equations.Properness and monotonicity are also identified as analytical requirements or properties in the framework.
  • Success and failure regions: State evolution converging to zero characterizes successful D-AMP recovery, while nonconvergence indicates failure.For monotone denoisers, success at one measurement density implies success at every larger density.
  • Success and failure regions: For small measurement ratios δ, D-AMP fails; beyond a threshold, it successfully recovers the signal from undersampled measurements.The minimum successful measurement ratio is denoted δ*(xo).
  • Proper denoisers: If a denoiser is proper at level κ for a signal class, D-AMP achieves exact recovery when δ > κ under the state-evolution framework.The proposition connects the required measurement density to the denoiser’s properness level.
  • Near proper denoisers: Near proper denoisers may prevent perfect recovery, but when δ > κ their asymptotic D-AMP error is bounded by B/(δ − κ).The bound applies to near proper denoiser families with levels κ and B.

E. Noise sensitivity of D-AMP

D-AMP remains robust to measurement noise, with state evolution providing a noise-sensitivity analysis and upper bound. In the noiseless case, recovery depends on the sampling rate, while worst-case bounds may be conservative.

  • Noise robustness: D-AMP is robust to measurement noise under near-proper denoisers.The analysis assumes a denoiser near proper at levels κ and B.
  • Noise sensitivity: With measurement noise, the fixed point is nonzero, so D-AMP does not recover the signal exactly.This motivates defining noise sensitivity through the fixed-point error.
  • Noise sensitivity: Proposition 2 upper-bounds D-AMP noise sensitivity as a function of measurements and measurement-noise variance.The stated condition is δ > κ.
  • Bound interpretation: The noise-sensitivity bound is worst-case, and most signals and noise variances yield better performance than the bound predicts.Figure 8 illustrates BM3D-AMP performance versus measurement-noise standard deviation.

F. Tuning the parameters of D-AMP

D-AMP’s parameter-tuning problem appears iterative, but greedy tuning is optimal under the stated framework. Consequently, tuning D-AMP is essentially the tuning problem of its denoiser.

  • Tuning challenge: Practical denoisers often contain free parameters whose effective tuning determines denoising performance.Soft-thresholding is given as a simple parameterized example.
  • Evaluation: BM3D-AMP performance is evaluated using MSE for the Barbara image across measurement-noise levels and sampling rates.The figure uses 128 × 128 Barbara reconstructions.
  • Tuning challenge: Jointly tuning parameters across iterations appears difficult because each iteration has a different effective noise level.Early iterations have larger effective-noise standard deviation than later iterations.
  • Greedy tuning: Greedy parameter tuning is optimal for D-AMP under the paper’s state-evolution formulation.The optimality is established through an induction argument.
  • Implications: Optimally tuned denoisers induce the best possible D-AMP performance, and existing denoising literature has already addressed this tuning problem.The paper notes that D-AMP can use established schemes such as SURE.

G. Optimality of D-AMP

The paper analyzes D-AMP optimality both uniformly across signal classes and within a single class. D-AMP is optimal for some classes but can be substantially sub-optimal for others.

  • Uniform optimality: Uniform optimality asks whether any recovery algorithm can outperform D-AMP across all signal classes in the considered family.The question is meaningful because denoisers may fail to capture all structures in a signal class.
  • Uniform optimality: D-AMP recovers every signal in classes Eκ using δ > κ measurements, while no algorithm can uniformly improve this requirement.The lower bound follows by considering κn-dimensional subspaces.
  • Single-class optimality: Single-class optimality evaluates D-AMP on one specified signal class, which the uniform framework cannot characterize.The paper introduces this framework for applications such as imaging.
  • Single-class optimality: For a fixed class, the optimal D-AMP denoiser minimizes the state-evolution fixed point, which corresponds to the final estimate’s mean square error.The optimal denoiser may depend on measurement-noise variance and sampling rate and need not be unique.
  • Single-class optimality: The minimax denoiser family is optimal for D-AMP, but fewer-observation recovery algorithms can still exist for particular classes.Proposition 4 establishes the denoiser-side optimality result before the counterexample.
  • Single-class optimality: For the class of signals containing k ones and n − k zeros, other algorithms can recover accurately from 1 measurement, whereas optimal D-AMP requires about nκMM measurements.Thus D-AMP can be sub-optimal for this class despite being optimal for other classes.

H. Additional miscellaneous properties of D-AMP

The paper connects D-AMP to state evolution, proximal methods, and optimal denoising. These connections support theoretical analysis, parameter tuning, and alternative implementations of the framework.

  • State evolution: The paper formalizes the claim that one denoiser’s uniformly lower state evolution yields a lower fixed point than another’s.Theorem 1 compares denoiser families through their state-evolution trajectories.
  • Regularization connection: D-AMP can be interpreted as a heuristic method for solving regularized inverse problems when the proximal operator is treated as a denoiser.Monte Carlo estimation can be used when explicitly calculating the Onsager correction is difficult.
  • State-evolution variants: The deterministic state evolution treats the signal as fixed, whereas Bayesian state evolution treats it as drawn from a probability density.Both frameworks generate scalar sequences from corresponding initial conditions.
  • Bayesian optimality: The conditional-mean denoiser E(x_o | x_o + σϵ) is Bayes-optimal for D-AMP at noise level σ^2.The paper relates deterministic and Bayesian analyses through minimax and Bayesian risk.

C. Connection between the two state evolutions

The paper connects Bayesian and deterministic state evolutions through their fixed points under suitable conditions, while emphasizing that deterministic state evolution applies to specific signals without requiring known distributions.

  • C. Connection between the two state evolutions: The supremum fixed point of Bayesian state evolution with Bayes-optimal denoisers equals that of deterministic state evolution with minimax denoisers.This equivalence holds under the stated general conditions.
  • C. Connection between the two state evolutions: The deterministic state evolution analyzes specific signals rather than signal distributions, making it useful when distributions are poorly understood.The paper highlights natural images as an example for which specifying an accurate probability density is difficult.
  • C. Connection between the two state evolutions: D-AMP analysis also requires calculating the Onsager correction for arbitrary denoisers, which is difficult when their input-output relations are implicit.The paper proposes approximating the divergence even without an explicit denoiser formulation.

2) Block soft-thresholding: τ

This section derives divergence-related tools for denoisers and addresses discontinuous denoisers by Gaussian smoothing, which restores continuity and improves state-evolution agreement and reconstruction.

  • VI. SMOOTHING A DENOISER: The state-evolution predictions fail for hard-thresholding-based D-AMP because hard thresholding is discontinuous.Smoothing removes the discontinuities while otherwise preserving the denoiser’s input-output behavior.
  • VI. SMOOTHING A DENOISER: Smoothed-hard-thresholding successfully reconstructs a sparse signal at sampling rate δ = 1/3, whereas hard-thresholding-based D-AMP does not.The paper attributes the failure of the unsmoothed method to the denoiser’s discontinuity.
  • VI. SMOOTHING A DENOISER: Gaussian convolution smooths a discontinuous denoiser, with larger kernel width r producing a smoother function.The smoothed denoiser is defined by convolving the original denoiser with a Gaussian kernel.
  • VI. SMOOTHING A DENOISER: A smoothed denoiser is continuously differentiable with bounded derivative, and therefore Lipschitz continuous, under the stated growth condition.This regularity is established by the smoothing lemma.
  • VI. SMOOTHING A DENOISER: The paper does not provide a general rule for selecting the smoothing parameter r, whose effect in AMP requires further rigorous analysis.This leaves parameter choice as a limitation of the smoothing approach.
  • VI. SMOOTHING A DENOISER: Smoothing makes D-AMP closely follow state evolution and enables use of the associated theory and tuning strategies, while advanced denoisers required no smoothing in the reported experiments.The authors report that advanced denoisers already satisfy state evolution and perform exceptionally without smoothing.

VII. SIMULATION RESULTS FOR IMAGING APPLICATIONS

The imaging experiments plug several denoisers into D-AMP, with parameter tuning adapted to iteration-dependent noise and comparisons based primarily on PSNR and reconstruction behavior.

  • VII. SIMULATION RESULTS FOR IMAGING APPLICATIONS: D-AMP uses denoising algorithms including Gaussian filtering, bilateral filtering, NLM, wavelet thresholding, and BM3D variants for imaging recovery.The paper names the resulting methods according to the denoiser used, such as NLM-AMP and BM3D-AMP.
  • VII. SIMULATION RESULTS FOR IMAGING APPLICATIONS: NLM generally outperforms bilateral filtering because neighborhood similarity better identifies alike pixels, although it can still create edge artifacts.The paper notes that similar neighborhoods across edges can cause these artifacts.
  • VII. SIMULATION RESULTS FOR IMAGING APPLICATIONS: D-AMP parameters can be tuned greedily by minimizing the MSE at each iteration, using denoising-specific parameter-setting strategies.This addresses the fact that optimal denoiser parameters may vary across iterations.
  • VII. SIMULATION RESULTS FOR IMAGING APPLICATIONS: For BM3D, BM3D-SAPCA, and BLS-GSM, the implementation estimates noise using ||z_t||^2/m and supplies that estimate to the denoising packages.Those packages internally tune their remaining parameters to minimize MSE.
  • VII. SIMULATION RESULTS FOR IMAGING APPLICATIONS: PSNR measures the rescaled MSE of both denoising and compressed-sensing recovery estimates.The paper defines PSNR for images with pixel range 0 to 255.

3) Stopping criterion:

D-AMP uses iterative denoising with an Onsager correction, and its effective noise is approximately Gaussian, enabling accurate state-evolution analysis. Experiments report strong recovery, robustness to measurement noise, and computation-time advantages, while iterations stabilize after roughly 30 steps.

  • 3) Stopping criterion:: After about 30 iterations, BM3D-AMP estimates have generally stabilized with low variance across sampling rates.PSNR often approaches its maximum by about 10 iterations, but estimate variance remains high until approximately iteration 30.
  • 3) Stopping criterion:: The Onsager correction helps keep D-AMP’s effective noise approximately Gaussian, supporting state-evolution prediction and parameter tuning.The effective noise’s Gaussianity also supports algorithm analysis and linear convergence of the iterates.
  • 3) Stopping criterion:: At iteration 29, state-evolution MSE predictions for AMP, NLM-AMP, BLS-GSM-AMP, and BM3D-AMP were all within 1.2% of observed MSEs.The comparison used a δ = 0.4 sampled 128×128 House image without measurement noise.
  • 3) Stopping criterion:: BM3D-AMP or BM3D-SAPCA-AMP outperformed all other compared algorithms in a large majority of noiseless tests.In one image comparison, BM3D-SAPCA-AMP achieved 29.96 dB versus 29.31 dB for NLR-CS and 20.07 dB for wavelet-sparsity AMP.
  • 3) Stopping criterion:: With measurement noise, D-AMP outperformed competing methods in almost all tests and exceeded them by as much as 7.4 dB in some tests.The BM3D-SAPCA-AMP and NLR-CS reconstructions scored 26.86 dB and 25.30 dB, respectively, in one noisy comparison.
  • 3) Stopping criterion:: Different denoisers let D-AMP trade off signal-model capture, reconstruction performance, and computation time.The BM3D variant was reported to be dramatically faster than NLR-CS and ALSB.

APPENDIX

The appendix analyzes fixed points and worst-case behavior of D-AMP’s state evolution, including an interpretation of least favorable signals for particular denoisers.

  • APPENDIX: The appendix compares fixed points of state evolution across denoisers and signals.Several proof steps establish inequalities between fixed points associated with different denoisers.
  • APPENDIX: For the analyzed denoiser, the least favorable D-AMP signal is also one of the least favorable signals for the denoiser itself.The paper states that the proof can be extended to any denoiser D_σ.

B. Proof of Proposition 5

The proof constructs a distribution concentrated near k-sparse signals, bounds its probability outside the sparse class, and uses this construction to derive a minimax-risk lower bound.

  • B. Proof of Proposition 5: The proof considers recovering a zero-one k-sparse signal x_o from noiseless measurements y = A x_o.The signal class is B_k, consisting of k-sparse vectors with zero-one elements.
  • B. Proof of Proposition 5: For the finite zero-one sparse signal space, incorrect estimates have squared error at most 2k, which bounds the error contribution.A union-bound argument establishes that the recovery error probability is zero in the stated setting.
  • B. Proof of Proposition 5: The constructed distribution produces samples in B_k with very high probability by applying Hoeffding’s inequality.The proof then conditions the distribution on the event that the sample has at most k nonzero entries.
  • B. Proof of Proposition 5: Conditioning the constructed distribution on the sparse event enables a lower bound for the minimax risk of every denoiser D_σ.The proof relates the conditioned and original distributions through the probability of the complementary event.
  • B. Proof of Proposition 5: The proof uses the Bayes denoiser as an optimal benchmark when evaluating the conditional estimation risk.The argument factors the prior distribution across coordinates and evaluates the resulting scalar denoising terms.
Loading 1406.4175v5…