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

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

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).

Introduction

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 valued for its "state evolution" property—in the large system limit, the error at each iteration behaves 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, which is impractical for clinical workflows.

Methodology: Variable Density AMP (VDAMP)

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 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.

Results and Evaluation

The algorithm was evaluated on a standard 512x512 Shepp-Logan phantom, artificially corrupted with complex Gaussian noise (40dB SNR). Sampling was performed using polynomial variable density at undersampling factors of 4x, 6x, and 8x.

Visual comparison of reconstruction quality and error maps for FISTA, SURE-IT, and VDAMP.

VDAMP demonstrated massive speedups and superior quantitative accuracy. It converges over 5x faster than the industry-standard FISTA algorithm and reaches a significantly lower Mean Squared Error. 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 contrast, FISTA only reached -19.3 dB, and a baseline SURE-IT method reached -16.6 dB.

Convergence speed and NMSE performance across different undersampling factors (4x, 6x, 8x).

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.

Discussion and Key Insights

The core innovation is the empirical discovery that state evolution can occur in variable density Fourier sampling, provided the noise is treated as colored. The residual error behaves like the ground truth corrupted by zero-mean Gaussian noise with a distinct variance for each wavelet scale.

SURE is a powerful statistical tool for automatic parameter tuning, but its mathematical validity relies 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. Furthermore, because VDAMP automates parameter selection via SURE, the model benefits from a much richer, more flexible regularization scheme without any added user burden.

Limitations and Future Work

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. Additionally, the algorithm assumes the noise variance estimator concentrates around its expectation, which imposes unstudied mathematical constraints on the sampling probability matrix.

Future directions include pairing VDAMP with more sophisticated image denoisers, such as 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},
}
Figure