Divergence Estimation in Message Passing algorithms

Nikolajs Skuratovs, Michael Davies

Introduction

In high-dimensional signal processing and compressed sensing, recovering a signal $x$ from noisy linear measurements $y = Ax + w$ is a core challenge. Scalable Message Passing (SMP) algorithms, such as Approximate Message Passing (AMP) and Vector AMP (VAMP), are widely used for this task due to their speed and predictable convergence behavior in the large system limit.

A critical component of these algorithms is the Onsager correction. This term ensures stability and correct convergence by accounting for the "divergence"—essentially the average sensitivity—of the denoiser used at each step. Traditionally, this divergence is estimated using the Black-Box Monte Carlo (BB-MC) method. However, BB-MC has significant drawbacks: it is computationally expensive, requiring at least one extra denoiser evaluation per iteration, and it can be mathematically fragile when used with modern, non-smooth denoisers like BM3D or ReLU-based neural networks.

Proposed Estimators

Nikolajs Skuratovs and Michael Davies propose two new classes of estimators that leverage Large System Limit (LSL) models to estimate divergence using data already present within the algorithm, thereby eliminating the need for BB-MC.

  1. Algebraic Divergence Estimator: This method uses the difference between residuals in current and previous iterations ($r_t - r_{t-1}$) to estimate divergence. Its computational cost is negligible, making it ideal for on-the-fly denoiser tuning.
  2. Polynomial Divergence Estimator: This more robust method formulates divergence estimation as finding the root of a specific quadratic equation. While it requires one additional matrix-vector product, it remains much faster than re-running a complex denoiser and offers superior stability at moderate signal dimensions.

The paper also introduces a "Root Identification" strategy to mathematically determine the correct root of the quadratic equation for the divergence estimate.

Experimental Evaluation

The researchers evaluated their methods using standard natural images, including the "man" and "birds" datasets at various resolutions.

Sample images used for evaluation: the "man" and "birds" datasets.

The experiments utilized both standard Random Gaussian matrices and the more challenging Fast ill-conditioned Johnson-Lindenstrauss Transform (FIJL) to test algorithm stability. The state-of-the-art BM3D denoiser was employed, providing a rigorous test for the estimators due to its non-smooth nature.

Key Results

The proposed estimators demonstrated significant improvements over the traditional BB-MC approach:

  • Speed: Algorithms using the polynomial estimator were nearly twice as fast as those using BB-MC because they eliminated redundant denoiser executions.
  • Stability: In tests with ill-conditioned matrices where SMP algorithms often fail, the proposed estimators maintained stable reconstruction.
  • Accuracy: The polynomial estimator consistently showed lower estimation error for the "oracle" divergence compared to both BB-MC and the simpler algebraic method.
Performance comparison between Polynomial and Algebraic estimators. The left plot shows Normalized Mean Square Error (NMSE) over iterations, while the right plot shows the relative divergence estimation error.

As illustrated above, the polynomial estimator provides a more accurate and stable estimate of the divergence, leading to improved signal reconstruction quality (NMSE) over time compared to the algebraic baseline.

Limitations and Future Work

While these estimators are exact in the Large System Limit ($N \to \infty$), their accuracy can degrade as the signal dimension $N$ decreases, with the algebraic estimator being particularly sensitive to finite-size effects. Furthermore, while the root identification strategy is proven for specific OAMP-based algorithms, a fully rigorous proof for standard AMP and CAMP cases remains a task for future work. Despite these limitations, these methods offer a robust and efficient alternative for high-dimensional signal recovery.

Summary updated

BibTeX
@article{skuratovs2023divergence,
  author = {Nikolajs Skuratovs and Michael Davies},
  title = {{Divergence Estimation in Message Passing algorithms}},
  journal = {IEEE Trans. Information Theory},
  year = {2023},
  doi = {10.1109/tit.2023.3291615},
}
Figure