| Markov chain Monte Carlo (MCMC) sampling has shown great potential in tackling complex integration and optimization problems, and thus has attracted much attention from the statistical community in the past two decades. Its recent use in signal processing has also stimulated growing interest among researchers. However, MCMC sampling has an problem in convergence diagnosis. This drawback of it had remained problematic for a long time until the proposal of the coupling from the past (CFTP) algorithm by Propp and Wilson [1] in 1996.; CFTP and its extensions, now known as perfect sampling algorithms, can detect the convergence of Markov chains, and thereby obtain samples exactly from desired distributions. Another direct result of knowing the convergence is that independent samples can also be acquired. Consequently, samples generated by perfect sampling algorithms fully comply with the conditions of optimal Monte Carlo integration, and therefore produce more accurate results.; In this dissertation, some important perfect sampling algorithms on both discrete and continuous variable spaces are carefully studied. In the investigation of perfect sampling on discrete variable spaces, we first employ the sandwiched CFTP to binary image restoration. However, most of the perfect sampling algorithms are very inefficient, and thus impractical. In order to use them to solve larger classes of problems in signal processing, new efficient algorithms have to be developed. With this objective and considering some specific engineering problems, we propose a new efficient perfect sampling algorithm on binary variable spaces, referred as the Gibbs coupler. We apply the Gibbs coupler, to multiuser detection of synchronous code-division multiple-access signals and variable selection. Furthermore, we combine the idea of the Gibbs coupler with the rejection coupler and propose a method for sampling from bounded high dimensional continuous spaces. We demonstrate the use of the method for perfect sampling from truncated multivariate Gaussian distributions. |
