Sequential Monte Cralo Particle Filtering

Arnaud Doucet, Nando de Freitas, and Neil Gordon

Little background on SMC.

Monte Carlo Method originally known as ‘method of statistical sampling’

ESTIMATION GENERAL CONCEPT

• Estimating unknown quantities from given observations. I.e.: Prior knowledge available.
• Able to formulate Bayesian Model which is the prior distribution for the unknown quantities and the likelihood function relating these quantities to the observations.
• Inferences on the unknown quantities are made from the posterior distribution obtained from Bayes’ Theorem.
• Often observations arrive sequentially in time and able to perform inference on-line. Therefore necessary to update the posterior distribution as data become available.
• Goal: Computational simplicity allows not having to store all data.
• Example
• Data model using linear Gaussian state space: derive the posterior distribution using Kalman Filter.
• Data model using partially observed state space Markov Chain: obtained analytical solution using Hidden Markov Model HMM Filter
• Estimation method such as Kalman Filter and Gaussian sum approximation is based on normal distribution fail to cover the non-Gaussianity and nonlinearity. While Grid-based filter based on deterministic numerical integration method is too computationally expensive to be used in high dimension.

SMC SOLUTION

• Able to handle very complex data, typically involving non-Gaussianity, nonlinearity which condition usually preclude analytic solution.
• Flexible, easy to implement, parallelizable and applicable in very general setting.
• Closely related algorithm: bootstrap filters, condensation, particle filters, Monte Carlo filters, interacting particle approximations, and survival of the fittest.