"Direct version" algorithm of Particle Filter

"Direct version" algorithm

The "direct version" algorithm is rather simple (compared to other particle filtering algorithms) and it uses composition and rejection. To generate a single sample x at k from :

1) Set p=1

2) Uniformly generate L from {1,...,P}

3) Generate a test from its distribution

4) Generate the probability of using from where y_k is the measured value

5) Generate another uniform u from [0,m_k]

6) Compare u and

6a) If u is larger then repeat from step 2

6b) If u is smaller then save as xk | k^(p) and increment p

7) If p > P then quit

The goal is to generate P "particles" at k using only the particles from k − 1. This requires that a Markov equation can be written (and computed) to generate a x_k based only upon x_{k − 1}. This algorithm uses composition of the P particles from k − 1 to generate a particle at k and repeats (steps 2-6) until P particles are generated at k.

This can be more easily visualized if x is viewed as a two-dimensional array. One dimension is k and the other dimensions is the particle number. For example, x(k,L) would be the L^th particle at k and can also be written (as done above in the algorithm). Step 3 generates a potential x_k based on a randomly chosen particle () at time k − 1 and rejects or accepts it in step 6. In other words, the x_k values are generated using the previously generated x_{k − 1}.