UC San Diego

Optimal detection is one of the most fundamental problems in communication and statistical signal processing. Nevertheless, in many applications, the optimal detection problem often reduces to an NP-complete, or even NP-hard, discrete optimization problem. This research project aims to develop randomized algorithms using Monte Carlo Markov chain methods to achieve near-optimal decision-making. In particular, this project focuses on two specific applications---signal detection in multiple-in-multiple-out systems and decoding of error correction codes. For the scenarios considered, we successfully proposed fast-converging Monte Carlo Markov chain algorithms that achieve near-optimality in reasonable iterations and outperform the previously best-known methods. These results open a new approach to optimal detection.