Auxiliary particle filter

The auxiliary particle filter is a particle filtering algorithm introduced by Pitt and Shephard in 1999 to improve some deficiencies of the sequential importance resampling (SIR) algorithm when dealing with tailed observation densities.

Assume that the filtered posterior is described by the following M weighted samples:

p(x_t|z_{1:t}) \approx \sum_{i=1}^M \omega^{(i)}_t \delta \left( x_t - x^{(i)}_t \right).

Then, each step in the algorithm consists of first drawing a sample of the particle index $k$ which will be propagated from $t-1$ into the new step $t$ . These indexes are auxiliary variables only used as an intermediary step, hence the name of the algorithm. The indexes are drawn according to the likelihood of some reference point $\mu^{(i)}_t$ which in some way is related to the transition model $x_t|x_{t-1}$ (for example, the mean, a sample, etc.):

k^{(i)} \sim P(i=k|z_t) \propto \omega^{(i)}_t p( z_t | \mu^{(i)}_t )

This is repeated for $i=1,2,\dots,M$ , and using these indexes we can now draw the conditional samples:

x_t^{(i)} \sim p( x | x^{k^{(i)}}_{t-1}).

Finally, the weights are updated to account for the mismatch between the likelihood at the actual sample and the predicted point $\mu_t^{k^{(i)}}$ :

\omega_t^{(i)} \propto \frac{p( z_t | x^{(i)}_t) } { p( z_t | \mu^{k^{(i)}}_t) }.

References

Pitt, M.K.; Shephard, N. (1999). "Filtering Via Simulation: Auxiliary Particle Filters". Journal of the American Statistical Association (American Statistical Association) 94 (446): 590–591. doi:10.2307/2670179. JSTOR 2670179. Retrieved 2008-05-06.