Auxiliary Variable Methods for Markov Chain Monte Carlo with Applications

Abstract Suppose that one wishes to sample from the density π(x) using Markov chain Monte Carlo (MCMC). An auxiliary variable u and its conditional distribution π(u|x) can be defined, giving the joint distribution π(x, u) = π(x)π(u|x). A MCMC scheme that samples over this joint distribution can lead to substantial gains in efficiency compared to standard approaches. The revolutionary algorithm of Swendsen and Wang is one such example. Besides reviewing the Swendsen-Wang algorithm and its generalizations, this article introduces a new auxiliary variable method called partial decoupling. Two applications in Bayesian image analysis are considered: a binary classification problem in which partial decoupling out performs Swendsen-Wang and single-site Metropolis methods, and a positron emission tomography (PET) reconstruction that uses the gray level prior of Geman and McClure. A generalized Swendsen–Wang algorithm is developed for this problem, which reduces the computing time to the point where MCMC is a viable method of posterior exploration.