Particle Filter - "Direct Version" Algorithm

"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 at from :

1) Set n=0 (This will count the number of particles generated so far)

2) Uniformly choose an index L from the range

3) Generate a test from the distribution

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

5) Generate another uniform u from where

6) Compare u and

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

6b) If u is smaller then save as and increment n

7) If n == P then quit

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

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