Approximate Message Passing Algorithms for Inference and Optimization
Lead Research Organisation:
University of Cambridge
Department Name: Engineering
Abstract
Message-passing algorithms are used for probabilistic inference in a variety of applications including communications, computer vision, and machine learning. Recently, there has been much interest in applying approximations of these algorithms to problems such as sparse regression and compressed sensing, where the dependence graph of the variables is dense. Despite empirical success in these settings, we do not have a sound theoretical understanding of approximate message-passing (AMP) yet. This project aims to theoretically characterize conditions under which does approximate message-passing works well. The project will also investigate applications of AMP to new settings such as capacity-achieving codes, sparse approximation, and data compression.
The project is relevant to multiple EPSRC research areas including, Digital signal processing, RF and microwave communications, and Statistics and Applied probability.
The project is relevant to multiple EPSRC research areas including, Digital signal processing, RF and microwave communications, and Statistics and Applied probability.
Organisations
People |
ORCID iD |
| Ramji Venkataramanan (Primary Supervisor) | |
| Kuan Hsieh (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509620/1 | 01/10/2016 | 30/09/2022 | |||
| 1769423 | Studentship | EP/N509620/1 | 01/10/2016 | 09/01/2021 | Kuan Hsieh |
| Description | Sparse regression codes (SPARCs) are a recent class of error-correcting codes proposed for communications over the additive white gaussian noise (AWGN) channel. It has been proven mathematically that such codes can achieve the capacity of the AWGN channel using a power allocation technique and approximate message passing (AMP) decoding. In this project, my collaborators and I have proved mathematically that SPARCs can achieve the capacity of the AWGN channel using a spatial coupling technique and AMP decoding. Furthermore, this project has extended SPARC encoder designs to incorporate standard digital modulation schemes such as Phase-Shift Keying (PSK), and proved similar capacity-achieving properties for these generalised SPARC designs. Through numerical simulations, this project demonstrated that the error rate versus signal-to-noise tradeoff achieved by SPARCs is competitive with that of state-of-the-art coded modulation communication schemes. |
| Exploitation Route | The research findings from the project suggests a capacity-achieving channel coding scheme with details of the encoder and decoder. Others may investigate the feasibility of this coding scheme in practice. For example, the encoding and decoding complexity and hardware requirements can be investigated. |
| Sectors | Digital/Communication/Information Technologies (including Software) |