216
C. Greco and M. Vasile
w
(i)
k =
p
x
(i)
0:k |y 1:k
π
x
(i)
0:k |y 1:k
=
p
y k |x
(i)
0:k , y 1:k−1
p
x
(i)
0:k |y 1:k−1
/p
y k |y 1:k−1
π
x
(i)
k |x
(i)
0:k−1 , y 1:k
π
x
(i)
0:k−1 |y 1:k−1
≈
p
y k |x
(i)
k
p
x
(i)
k |x
(i)
0:k−1 , y 1:k−1
p
x
(i)
0:k−1 |y 1:k−1
π
x
(i)
k |x
(i)
0:k−1 , y 1:k
π
x
(i)
0:k−1 |y 1:k−1
=
p
y k |x
(i)
k
p
x
(i)
k |x
(i)
k−1
π
x
(i)
k |x
(i)
0:k−1 , y 1:k
p
x
(i)
0:k−1 |y 1:k−1
π
x
(i)
0:k−1 |y 1:k−1
= w
(i)
k−1
p
y k |x
(i)
k
p
x
(i)
k |x
(i)
k−1
π
x
(i)
k |x
(i)
0:k−1 , y 1:k
,
(6.88)
where the Markov properties (6.7)–(6.8) have been used. The normalisation quantity
p(y k |y 1:k−1 ) has disappeared because when the weights are normalised to sum
to unity, w
(i)∗
k
= w
(i)
k /
j w
(j )
k , it cancels out regardless. From the problem
formulation in Eq. (6.73), and because π(·) should be chosen to be simple to
sample from, it is straightforward to evaluate this weight update equation. As in
Sect. 6.2.2.3, the importance sampling was chosen to decompose as:
π
x
(i)
0:k |y 1:k
= π
x
(i)
k |x
(i)
0:k−1 , y 1:k
π
x
(i)
0:k−1 |y 1:k−1
.
(6.89)
This choice is key in the sequential algorithm, as the sample x
(i)
0:k from π(x
(i)
0:k |y 1:k )
can be obtained by simply augmenting x
(i)
0:k−1 from π(x
(i)
0:k−1 |y 1:k−1 ) with x
(i)
k from
π(x
(i)
k |x
(i)
0:k−1 , y 1:k ), avoiding therefore to sample the full joint distribution [3].
With the developed sequential framework, the general scheme of a particle filter
algorithm is given in Algorithm 6. There are infinite ways to choose the importance
Algorithm 6 Particle filter (no resampling)
Given the filtering model in Eq. (6.73)
1: Draw N particles x
(i)
0 ∼ p(x 0 ), with equal weights w
(i)
0 = 1/N
2: for k=1:Observation times do
3:
Sample new particles x
(i)
k and augment vector x
(i)
0:k = [x
(i)
0:k−1 , x
(i)
k ]
x
(i)
k ∼ π(x k |x
(i)
0:k−1 , y 1:k )
4:
Compute corresponding weights w
(i)
k and normalise to w
(i)∗
k
w
(i)
k = w
(i)
k−1 · p(y k |x
(i)
k )p(x
(i)
k |x
(i)
k−1 )/π(x
(i)
k |x
(i)
0:k−1 , y 1:k )
w
(i)∗
k
= w
(i)
k /
j w
(j )
k
5: end for
C. Greco and M. Vasile
w
(i)
k =
p
x
(i)
0:k |y 1:k
π
x
(i)
0:k |y 1:k
=
p
y k |x
(i)
0:k , y 1:k−1
p
x
(i)
0:k |y 1:k−1
/p
y k |y 1:k−1
π
x
(i)
k |x
(i)
0:k−1 , y 1:k
π
x
(i)
0:k−1 |y 1:k−1
≈
p
y k |x
(i)
k
p
x
(i)
k |x
(i)
0:k−1 , y 1:k−1
p
x
(i)
0:k−1 |y 1:k−1
π
x
(i)
k |x
(i)
0:k−1 , y 1:k
π
x
(i)
0:k−1 |y 1:k−1
=
p
y k |x
(i)
k
p
x
(i)
k |x
(i)
k−1
π
x
(i)
k |x
(i)
0:k−1 , y 1:k
p
x
(i)
0:k−1 |y 1:k−1
π
x
(i)
0:k−1 |y 1:k−1
= w
(i)
k−1
p
y k |x
(i)
k
p
x
(i)
k |x
(i)
k−1
π
x
(i)
k |x
(i)
0:k−1 , y 1:k
,
(6.88)
where the Markov properties (6.7)–(6.8) have been used. The normalisation quantity
p(y k |y 1:k−1 ) has disappeared because when the weights are normalised to sum
to unity, w
(i)∗
k
= w
(i)
k /
j w
(j )
k , it cancels out regardless. From the problem
formulation in Eq. (6.73), and because π(·) should be chosen to be simple to
sample from, it is straightforward to evaluate this weight update equation. As in
Sect. 6.2.2.3, the importance sampling was chosen to decompose as:
π
x
(i)
0:k |y 1:k
= π
x
(i)
k |x
(i)
0:k−1 , y 1:k
π
x
(i)
0:k−1 |y 1:k−1
.
(6.89)
This choice is key in the sequential algorithm, as the sample x
(i)
0:k from π(x
(i)
0:k |y 1:k )
can be obtained by simply augmenting x
(i)
0:k−1 from π(x
(i)
0:k−1 |y 1:k−1 ) with x
(i)
k from
π(x
(i)
k |x
(i)
0:k−1 , y 1:k ), avoiding therefore to sample the full joint distribution [3].
With the developed sequential framework, the general scheme of a particle filter
algorithm is given in Algorithm 6. There are infinite ways to choose the importance
Algorithm 6 Particle filter (no resampling)
Given the filtering model in Eq. (6.73)
1: Draw N particles x
(i)
0 ∼ p(x 0 ), with equal weights w
(i)
0 = 1/N
2: for k=1:Observation times do
3:
Sample new particles x
(i)
k and augment vector x
(i)
0:k = [x
(i)
0:k−1 , x
(i)
k ]
x
(i)
k ∼ π(x k |x
(i)
0:k−1 , y 1:k )
4:
Compute corresponding weights w
(i)
k and normalise to w
(i)∗
k
w
(i)
k = w
(i)
k−1 · p(y k |x
(i)
k )p(x
(i)
k |x
(i)
k−1 )/π(x
(i)
k |x
(i)
0:k−1 , y 1:k )
w
(i)∗
k
= w
(i)
k /
j w
(j )
k
5: end for