Divergence Estimation in Message Passing algorithms

Nikolajs Skuratovs, Michael Davies

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Many modern imaging applications can be modeled as compressed sensing linear inverse problems. When the measurement operator involved in the inverse problem is sufficiently random, denoising Scalable Message Passing (SMP) algorithms have a potential to demonstrate high efficiency in recovering compressed data. One of the key components enabling SMP to achieve fast convergence, stability and predictable dynamics is the Onsager correction that must be updated at each iteration of the algorithm. This correction involves the denoiser's divergence that is traditionally estimated via the Black-Box Monte Carlo (BB-MC) method. While the BB-MC method demonstrates satisfying accuracy of estimation, it requires heuristic tuning and executing the denoiser additional times at each iteration and might lead to a substantial increase in computational cost of the SMP algorithms. In this work we develop two Large System Limit models of the Onsager correction for denoisers operating within SMP algorithms and use these models to propose practical black-box methods for divergence estimation that require no additional executions of the denoiser and demonstrate similar correction compared to the BB-MC method.

Original languageEnglish
Pages (from-to)7461-7477
Number of pages17
JournalIEEE Transactions on Information Theory
Issue number11
Early online date3 Jul 2023
Publication statusPublished - 1 Nov 2023

Keywords / Materials (for Non-textual outputs)

  • cs.IT
  • math.IT
  • message passing
  • Divergence Estimation
  • Denoiser
  • Onsager Correction
  • expectation propagation
  • denoiser
  • Message passing
  • divergence estimation
  • Onsager correction


Dive into the research topics of 'Divergence Estimation in Message Passing algorithms'. Together they form a unique fingerprint.

Cite this