Summary: Suppose that one wishes to sample from the density \(\pi(x)\) using Markov chain Monte Carlo (MCMC). An auxiliary variable \(u\) and its conditional distribution \(\pi(u |x)\) can be defined, giving the joint distribution \(\pi(x, u)= \pi(x)\pi(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 R.H. Swendsen and J.-S. Wang [Phys. Rev. Lett. 58, 86-88 (1987)] 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 outperforms Swendsen-Wang and single-site Metropolis methods, and a positron emission tomography (PET) reconstruction that uses the gray level prior of S. Geman and D. McClure [Bull. Int. Stat. Inst. 52, 5-21 (1987)]. 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.