Divergence Estimation in Message Passing Algorithms

Nikolajs Skuratovs, Mike E. Davies

TL;DR

This paper tackles the challenge of efficiently estimating the divergence of denoisers within Message Passing (MP) algorithms, a crucial component for stable and fast signal recovery in compressed sensing. The authors propose two novel, data-driven divergence estimators that avoid costly re-executions of the denoiser, offering significant speedups and comparable or superior accuracy to existing methods, especially in large-scale problems.

What Problem Does This Paper Address?

Modern imaging applications, particularly in compressed sensing, often rely on iterative algorithms to reconstruct signals from incomplete measurements. Scalable Message Passing (SMP) algorithms are a powerful class of such methods, but their performance hinges on an "Onsager correction" that requires estimating the divergence of a denoiser at each iteration. The standard method, Black-Box Monte Carlo (BB-MC), is computationally expensive as it requires multiple denoiser evaluations per iteration. This becomes a bottleneck, especially when using complex, state-of-the-art denoisers like BM3D. The paper aims to develop faster and more efficient divergence estimators that can be computed using only the observed data within the algorithm, thus accelerating SMP and potentially improving their performance.

Methods

The paper introduces two novel divergence estimators:

  • Algebraic Divergence Estimator: This method leverages Large System Limit (LSL) models to derive a closed-form expression for the divergence. It relies on algebraic manipulations of the error dynamics within the MP algorithm and requires only one inner-product with the denoiser's output and the measurement operator per iteration. This makes it computationally very cheap.
  • Polynomial Divergence Estimator: This approach also uses LSL models but constructs a quadratic equation whose roots are related to the divergence. By analyzing the properties of this quadratic equation, the authors propose a method to identify the correct root, which corresponds to the divergence. This estimator's computational cost is dominated by two matrix-vector products involving the denoiser's output and the measurement operator.

Both methods are derived under LSL assumptions but are shown to be stable and accurate even for finite dimensions. The paper also provides a strategy for identifying the correct root of the polynomial estimator, particularly when the roots are complex.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and simulation-based evaluation using synthetic data and natural images as ground truth signals.

Key Insights and Ideas

  • Divergence Estimation is Key: The paper reinforces the critical role of accurate and efficient divergence estimation for the stability and performance of SMP algorithms.
  • BB-MC Bottleneck: The computational cost of the standard BB-MC method is a significant limitation, especially for complex denoisers.
  • Data-Driven, Denoiser-Agnostic: The proposed estimators do not require knowledge of the denoiser's internal workings beyond its input-output behavior, making them broadly applicable.
  • LSL as a Powerful Tool: The use of Large System Limit (LSL) models is instrumental in deriving tractable and efficient estimators from complex iterative algorithms.
  • Trade-offs in Estimators: The algebraic estimator is extremely fast but can be sensitive to finite dimensions, while the polynomial estimator offers better robustness at lower dimensions at a slightly higher computational cost.

Key Results

  • The proposed algebraic and polynomial divergence estimators significantly reduce the computational cost of SMP algorithms compared to the BB-MC method, often by avoiding additional denoiser executions.
  • In simulations, the polynomial estimator demonstrated comparable or superior accuracy in estimating the "oracle" correction compared to BB-MC, especially for large-scale problems.
  • The algebraic estimator with rt = rt-1 showed good performance but was less robust than the polynomial estimator at lower dimensions.
  • The polynomial estimator enabled stable dynamics for algorithms like CG-VAMP and WS-CG-VAMP, even when these algorithms slightly violated the theoretical assumptions (e.g., State Evolution).
  • The paper suggests a hybrid approach: using the algebraic estimator for denoiser tuning via SURE and the polynomial estimator for the final correction scalar to achieve both efficiency and stability.

Limitations and Future Work

  • Finite Dimensionality Error: While the proposed estimators are exact in the LSL, their accuracy can suffer from additional stochastic error in finite-dimensional settings. The paper notes that the polynomial estimator is more robust to decreased dimensionality than the algebraic one.
  • Root Identification Rigor: The theoretical identification of the correct root for the polynomial estimator is not fully rigorous for all cases. While empirical results consistently showed the derivative to be positive and the quadratic coefficient u3 to be negative (implying the smallest root is correct), a general proof is still needed.
  • Generalizing Proofs: The current proof techniques for root identification are specific to certain OAMP-based algorithms. Extending these proofs to a broader range of SMP algorithms is a future direction.
  • Optimizing Weights: The paper suggests further study into the optimal choice of weights for the algebraic estimator to improve its robustness.
  • Investigating Robustness: Understanding why the polynomial estimator is more robust to dimensionality and exploring ways to improve the algebraic estimator's robustness are key future research avenues.

Summary updated

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