Efficient Markov chain Monte Carlo inference in composite models with space alternating data augmentation

Space alternating data augmentation (SADA) was proposed by Doucet et al (2005) as a MCMC generalization of the SAGE algorithm of Fessler and Hero (1994), itself a famous variant of the EM algorithm. While SADA had previously been applied to inference in Gaussian mixture models, we show this sampler to be particularly well suited for models having a composite structure, i.e., when the data may be written as a sum of latent components. The SADA sampler is shown to have favorable mixing properties and lesser storage requirement when compared to standard Gibbs sampling. We provide new alternative proofs of correctness of SADA and report results on sparse linear regression and nonnegative matrix factorization.