An Approximate Message Passing Algorithm For Rapid Parameter-Free Compressed Sensing MRI

Charles Millard, Aaron T. Hess, Boris Mailhé, Jared Tanner

TL;DR

Approximate Message Passing (AMP) algorithms are notoriously unstable for MRI reconstruction due to the variable density sampling of Fourier coefficients. This paper introduces Variable Density AMP (VDAMP), which models the algorithm's internal error as "colored" rather than "white" noise, restoring predictable algorithmic behavior and enabling the use of Stein's Unbiased Risk Estimate (SURE) to create a rapid, completely parameter-free MRI reconstruction tool.

What Problem Does This Paper Address?

In compressed sensing MRI, images are reconstructed from undersampled Fourier data to speed up scan times. A popular class of algorithms for linear regression problems is Approximate Message Passing (AMP). AMP is beloved for a property called "state evolution"—in the large system limit, the error at each iteration behaves exactly like simple, additive Gaussian noise. This predictability allows for incredibly fast convergence.

However, standard AMP (and its variants like VAMP and OAMP) assumes this effective noise is "white" (having a uniform variance). In MRI, we sample low frequencies much more often than high frequencies (variable density sampling), and natural images have non-uniform spectral densities. This mismatch makes the effective noise "colored" (varying across different frequencies/wavelet subbands). Consequently, standard AMP algorithms lose their state evolution guarantees and frequently diverge or perform poorly in MRI settings. Furthermore, standard MRI reconstruction requires tedious manual tuning of regularization parameters (like sparsity weights), which is impractical for clinical workflows.

Methods

The authors develop Variable Density AMP (VDAMP), building on the Orthogonal AMP (OAMP) framework, with three major modifications:

  1. Density Compensation: VDAMP normalizes the sensing matrix using a diagonal matrix of the sampling probabilities. This ensures that the signal estimate remains unbiased right from the first iteration.
  2. Colored Noise Modeling: Instead of tracking a single scalar variance for the effective noise, VDAMP tracks a vector of variances—one for each wavelet subband (scale and direction).
  3. Parameter-Free Denoising via SURE: Because VDAMP successfully forces the error in each subband to be reliably Gaussian, the authors can use Stein's Unbiased Risk Estimate (SURE). SURE automatically calculates the optimal soft-thresholding parameters for each subband at every iteration, eliminating the need for hand-tuned regularization parameters.

Datasets

The authors evaluated their algorithm on simulated data:

  • Image: A standard 512x512 Shepp-Logan phantom.
  • Corruption: Artificially corrupted with complex Gaussian noise (40dB SNR).
  • Sampling: Sampled using polynomial variable density at undersampling factors of 4x, 6x, and 8x.

(Note: No novel benchmark datasets were introduced; the focus is on algorithmic validation on standard simulated phantoms).

Key Insights and Ideas

  • Colored State Evolution is Possible: The biggest "aha" moment is the empirical discovery that state evolution can occur in variable density Fourier sampling, provided you treat the noise as colored. The residual error behaves exactly like the ground truth corrupted by zero-mean Gaussian noise, just with a distinct variance for each wavelet scale.
  • SURE Needs Strict Gaussianity: SURE is a powerful statistical tool for automatic parameter tuning, but its math relies heavily on the underlying noise being Gaussian. Previous attempts to use SURE with algorithms like FISTA failed to reach optimal performance because FISTA's internal noise is highly non-Gaussian. VDAMP's strict Gaussian state evolution makes SURE mathematically sound and highly effective.
  • Rich Regularization for Free: Manually tuning a different sparsity weight for every single wavelet subband is practically impossible for a human. Because VDAMP automates this via SURE, the model benefits from a much richer, more flexible regularization scheme without any added user burden.

Key Results

  • Massive Speedups: VDAMP converges over 5x faster than the industry-standard FISTA algorithm and reaches a significantly lower Mean Squared Error.
  • Quantitative Accuracy: At an aggressive 8x undersampling factor, after just 2 seconds of compute time, VDAMP achieved a Normalized Mean Squared Error (NMSE) of -34.9 dB. In stark contrast, FISTA only reached -19.3 dB, and a baseline SURE-IT method reached -16.6 dB.
  • Compute Overhead: While VDAMP's per-iteration compute time is slightly longer than FISTA's (0.091s vs. 0.065s), its massive reduction in the total number of required iterations makes it vastly faster overall.

Limitations and Future Work

  • Lack of Theoretical Proof: The "colored state evolution" for this specific variable density Fourier setup is currently only empirically observed. A rigorous mathematical proof establishing the generality of this state evolution is left for future work.
  • Sampling Matrix Constraints: The algorithm assumes the noise variance estimator concentrates around its expectation, which imposes unstudied mathematical constraints on the sampling probability matrix.
  • Future Directions: The authors suggest pairing VDAMP with more sophisticated, state-of-the-art image denoisers (like neural networks in a Plug-and-Play framework). Since VDAMP guarantees the noise will be colored Gaussian, a neural network specifically trained to remove known colored Gaussian noise should yield even better MRI reconstructions.

Summary updated

Abstract

For certain sensing matrices, the Approximate Message Passing (AMP) algorithm efficiently reconstructs undersampled signals. However, in Magnetic Resonance Imaging (MRI), where Fourier coefficients of a natural image are sampled with variable density, AMP encounters convergence problems. In response we present an algorithm based on Orthogonal AMP constructed specifically for variable density partial Fourier sensing matrices. For the first time in this setting a state evolution has been observed. A practical advantage of state evolution is that Stein's Unbiased Risk Estimate (SURE) can be effectively implemented, yielding an algorithm with no free parameters. We empirically evaluate the effectiveness of the parameter-free algorithm on simulated data and find that it converges over 5x faster and to a lower mean-squared error solution than Fast Iterative Shrinkage-Thresholding (FISTA).
BibTeX
@inproceedings{millard2020approximate,
  author = {Charles Millard and Aaron T. Hess and Boris Mailhé and Jared Tanner},
  title = {{An Approximate Message Passing Algorithm For Rapid Parameter-Free Compressed Sensing MRI}},
  booktitle = {ICIP},
  year = {2020},
  url = {https://openreview.net/forum?id=KmkGlpE0jxJ},
}

Loading related content...

Figure