An optimal data ordering scheme for Dirichlet process mixture models

In recent years, there has been increasing interest in Bayesian nonparametric methods due to their flexibility, and the availability of Markov chain Monte Carlo (MCMC) methods for sampling from the posterior distribution. As MCMC methods are generally time consuming for computation, there is a need for faster methods, which can be executed within a matter of seconds. A fast alternative to MCMC for sampling the well known and widely used Dirichlet process mixture (DPM) model is investigated to draw approximate independent and identically distributed samples from the posterior distribution of the latent allocations, and then to draw samples from the weights and locations conditional on the allocations. To address the order depend issue of the proposed algorithm, an optimal ordering scheme based on a sequence of optimizations is proposed to first obtain an optimal order of the data, and then run the algorithm on this ordering. The fast sampling algorithm is assisted by parallel computing using commands within MATLAB.