Particle Filter

M4S4 Enhanced Coursework Particle Filters

Quang Phan CID: 00470370 May 7, 2010

1

1

1.1

Introduction

What is Particle Filters?

Filtering has many applications in real life, lying in the fields of signal processing, applied statistics, time series analysis and econometrics. It is the situation where we have some observed data, {Yn }, and an unobserved state space, {Xn }, which is assumed to be a Markov process Our objective is to use the observed data to estimate the distribution {Xn } . This can be done using this recursive formula: p(x0:n+1 |y0:n+1 ) = p(x0:n |y0:n ) p(y0:n+1 |x0:n+1 )p(xn+1 |xn ) p(yn+1 |y0:n )

This process is called filtering, allow us to calculate p(x0:n+1 |y0:n+1 ) based on p(x0:n |y0:n ). However, such formula is not usually done analytically unless the processes are Normal or linear, so numerical method is used to approximate. This is called particle filters. One possible approach is to use the importance (i) sampling, in which samples {x0:n , i = 1 : N } are drawn independently from (i) π(x0:n |y0:n ) with weights wn . This would allow us to obtain the approximation for the expectations of any functions fn (x0:n ). Of course the question is how to choose the importance function π(x0:n |y0:n ), this matter will be discussed below.

1.2

Expectation estimation

Suppose we know the distribution p(x0:n |y0:n ), then we can have an formula for expectation of any function of x0:n . E(fn (.)) = fn (.)p(x0:n |y0:n )dx0:n

The expression above may not be evaluated analytically, therefore we need a Monte Carlo approximation. Given the weights of all particles samples from π(x0:n |y0:n ), we can estimate the integral above as:

N (i) fn (.)wn j=1

We need a method to calculate the weights recursively in time, and this can be done using sequential Monte Carlo filtering.

1.3

Sequential Monte Carlo filter

The algorithm for evaluate the weights is shown below: For times n = 0, 1, 2... 2

• Sample {x0:n , i = 1 : N }...