Theoretical performance limits for message passing algorithms

Message passing algorithms are low-complexity algorithms that achieve state-of-the-art empirical performance in a variety of applications such as error correction and lossy compression. However, they lack theoretical performance guarantees in many of these applications. This project will analyse the performance of message algorithms by developing rigorous density evolution equations. We will start with the problem of lossy compression, and then extend the techniques to other approximation and inference problems.

The project directly relates to several EPSRC themes: Information and Communications Technologies (ICT), Engineering, Mathematical Sciences, and Healthcare Technologies, by making a strong contribution to the following research areas within these themes: Digital Signal Processing, Statistics and Applied Probability. It will help maintain UK academic excellence in data science by addressing an important set of research questions at the intersection of signal processing, information theory, and machine learning.