I. J. Communications, Network and System Sciences. 2008; 1: 1-103
Published Online February 2008 in SciRes (http://www.SRPublishing.org/journal/ijcns/).
Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103
Particle Filtering with Multi Proposal
Distributions
Fasheng WANG1,2, Qingjie ZHAO2, Yingbo ZHANG1, Liqun ZHANG2
1Neusoft Institute of Information, Northeastern University, P.R.China
2Beijing Key Lab of Intelligent Information
School of Computer Science and Technology, Beijing Institute of Technology, P.R.China
E-mail: {wangfasheng, zhangyingbo}@neusoft.edu.cn
{zhaoqj, wangfasheng, zhangliqun}@bit.edu.cn
Abstract
Particle filtering algorithm has been applied to various fields due to its capacity to handle nonlinear/non-Gaussian
dynamic problems. One crucial issue in particle filtering is the selection of the proposal distribution that generates the
particles. In this paper, we give a novel strategy for selecting proposal distribution. Firstly, divide-conquer strategy is
used, in which the particles used are divided into several parts. Afterward, different parts of particles are drawn from
different proposal distributions. People can flexibly adjust how many of the particles drawn from specific proposal
distributions according to their idiographic requirements. We provide simulation results that show its efficiency and
performance.
Keywords: Sequential Monte Carlo, Proposal Distribution, Multiple Proposal Distributions
1. Introduction
As is known to all, most important real world
applications are nonlinear and/or non-Gaussian.
Nonlinear filtering problems exist in many fields
including statistical signal processing, bio-statistics,
economics, and engineering such as communications,
radar tracking, sonar ranging, target tracking, car
positioning, robot localization, and so on [1]. There are a
variety of solutions for these problems, among which the
extended Kalman filter (EKF) is well known. This kind of
filters is based on linearizing technique that linearize the
process model and measurement model by using Taylor
series expansions. However, it is likely to diverge when
the linearizing approximation methods give poor
representations of the nonlinear functions.
The unscented Kalman filter (UKF) is another kind of
interesting solutions, which is founded on the fact that it
is easier to approximate a Gaussian distribution than it is
to approximate an arbitrary nonlinear function [12][15].
Unlike the EKF, the UKF does not use the approximated
models of the nonlinear process and the observation, but
approximates the distribution of the state random variable
by using a set of samples. It is shown that the UKF can
acquire more accurate estimation results than the EKF can,
This work was supported by the National Natural Science foundation
of China, Granted NO.60772063
but might lead to notable errors for non-Gaussian
distributions.
In recent years, particle filters have drawn much
attention in adaptive processing of nonlinear and non-
Gaussian problems. It has been proved that the
performance of particle filter is much better than
traditional nonlinear filtering methods, such as the EKF,
UKF, etc. [2][3].
The basic idea of particle filtering algorithm is to
represent the required probability density function (PDF)
by a set of random samples with associated weights. In
the past decades, this method has been applied with great
success to a variety of nonlinear/non-Gaussian filtering
problems that was raised in communication fields, such as
channel equalization [4], problems in MIMO wireless
communication [5][6], phase tracking [7], problems in
digital communication [19] etc. In addition, it is also
widely used in vision tracking [3], robot localization [8-
10], positioning and navigating [11], and so on.
A key issue in particle filtering algorithm is the
selection of the proposal distribution which is generally
hard to design. There are many proposal distributions
proposed in the literature, among which the EKF [12][13]
and the UKF [15] are well-known, as well as the
transition prior [16]. Using EKF and UKF as proposal
distributions, we get the Extended Kalman Particle Filter
(EKPF) and the Unscented Particle Filter (UPF) [12][15],
PARTICLE FILTERING WITH MULTI PROPOSAL DISTRIBUTIONS 23
Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103
respectively. The famous CONDENSATION algorithm
uses transition prior as the proposal distribution [16]. But
the EKPF can diverge for strong nonlinearity cases, while
the UPF is not applicable to general non-Gaussian model
and has very high time cost. The CONDENSATION
algorithm does not use the latest incoming information
which contains very valuable data.
In order to solve the problems that are encountered by
several existing particle filters, in this paper, we give a
multi-proposal-distribution based particle filter, which is
based on the EKF, UKF, and the transition prior. The
particles used in the experiments are firstly divided into
two parts, with one part (c percent) drawn from the EKF
and UKF, another part (1-c percent) drawn from the
transition prior. It gives not only higher accuracy but also
lower time with proper choice of c.
The remainder of the paper is organized as follows. In
Section 2, we give a brief introduction of particle filtering
algorithm. The multi-proposal-distribution based particle
filter (MPD-PF) is given in Section 3. Section 4 shows
the simulation results. Conclusions are drawn in Section 5.
2. Particle Filtering
We adopt the following dynamical models:
),( 11 −−
=kkkk vxfx (1)
),(kkkk uxhz = (2)
where xkx
n
R
denotes the system state at time k, and zk
z
n
R
denotes the observations at time k. The functions
k
fand k
hare the system transition model function and
measurement model function respectively. The noise
processes are vk and uk, the process noise and
measurement noise, respectively.
According to the basic idea of particle filters,
let N
i
i
k
i
kwx 1:0 },{ =denotes a random measure used to
represent the posterior density function p(x0:k|z1:k).
},...,0,{ :0 Nixi
k= is a set of support particles with
associated weights {i
k
w, i=0,…,N}, and x0:k show the
states up to time k. When N tends to the infinity, the
posterior density function can be approximated by:
=
−≈ N
i
i
kk
i
kkk xxwzxp
1
:0:0:1:0 )()|(
δ
(3)
where δ(.) denotes the Dirac delta function.
Many of the particle filters rely on the principle of
importance sampling [17]. Because it is usually difficult
to directly draw particles from the posterior density, we
can generate particles from a proposal distribution density
function q(), which is also known as an importance
function, and the weights are assigned according to:
)(/)|( :1:0 ⋅= qzxpw kk
i
k (4)
So the choice of proposal distribution q(.) is of great
importance. Assume the particles i
k
x:0 are drawn from an
importance density q(x0:k|z1:k). Considering the following
factorization:
)|(),|()|( 1:11:0:11:0:1:0 −−−
=
kkkkkkk zxqzxxqzxq (5)
Suppose we have gotten the approximation of the
posterior distribution at time k-1, that is, p(x0:k-1|z1:k-1) can
be represented by the particle set N
i
i
k
i
kwx 111:0 },{ =−− , which
are drawn from i
k
x1:0 ~ )|(1:01:0 −− kk yxq. The particle
weights are computed by using the formula:
)|(/)|(1:11:01:11:01 −−−−− =k
i
kk
i
k
i
kzxqzxpw (6)
In the following step, we aim to obtain N
i
i
k
i
kwx 1:0},{ =
using the new observation zk. So long as we get the
particles i
k
x and augment them onto the old particle
trajectory, the new trajectory can be acquired. The new
particles are generated as follows:
),|(~ :01:0 k
i
kk
i
kzxxqx (7)
The recursive equation for calculating weights can be
obtained using Bayesian rules:
),|(
)|()|(
1
1
1
k
i
k
i
k
i
k
i
k
i
kk
i
k
i
kzxxq
xxpxzp
ww
(8)
Generally, the generic particle filter uses the transition
prior p(xk|xk-1)as the importance density function [12][16].
It has been proved that the proposal distribution
),|(),|( :11:0:11:0 kkkkkk zxxpzxxq−− = is optimal [12].
One of the drawbacks of particle filter is degeneracy
problems. After several iterations, all but one particle
would probably have negligible weights. In order to solve
the problem, the resampling method is introduced [17],
[18]. There are several resampling methods, such as
systematic resampling, residual resmapling, etc. In this
paper, the residual resampling method is used for all the
experiments.
The generic particle filtering algorithm can be shown
as algorithm 1.
24 F.S. WANG ET AL.
Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103
3. MPD-Based Particle Filter
The particles used are firstly divided into two parts – c
percent and 1-c percent. The MPD-PF first uses a mixed
Kalman filter, which combines the UKF and the EKF, to
draw c percent the particles. Afterwards, it uses its
transition prior for another part – 1-c percent. Choice of c
can affect the performance of the MPD-PF greatly. But
one can choose it flexibly according to practical
requirement.
For the c percent particles, suppose we have obtained
the estimates of the state and the corresponding
covariance at time k-1, )(
1
i
k
xand )(
1
ˆi
k
P. At the next time
step k, the UKF is firstly used to update the particles.
The sigma points used in this process are calculated
using the equation (see [12]),
ai
k
)(
1
χ
=[ ai
k
x)(
1 ai
ka
ai
kPnx )(
1
)(
1)( −−
λ
] (9)
The particles are propagated into the future through
the nonlinear models (equation (1) and (2)),
),( )(
1
)(
1
)(
1|
vi
k
xi
k
xi
kkf−−− =
χχχ
),( )(
1
)(
1|
)(
1|
ui
k
xi
kk
i
kkhZ−−− =
χχ
(10)
The predicted state and corresponding covariance can
be obtained,
=
−− =a
n
j
xi
kkj
m
j
ukf
i
kkWx
2
0
)(
1|,
)()(
1|
χ
(11)
=
−−−−− −−= a
n
j
T
ukf
i
kk
xi
kkj
ukf
i
kk
xi
kkj
c
j
ukf
i
kk xxWP
2
0
)(
1|
)(
1|,
)(
1|
)(
1|,
)()(
1| ]][[
χχ
(12)
where )(m
j
W and )(c
j
W are weights of sigma points (see
[12] and [14]), na=nx+nv+nu. And, the predicted
measurement can be computed using,
=
−− =a
n
jukf
i
kkj
m
j
ukf
i
kk ZWz
2
0
)(
1|,
)()(
1| (13)
If a new measurement zk is obtained, update the
predicted estimates as follow,
)( )(
1|
)(
1|
)(
ukf
i
kkkk
ukf
i
kk
ukf
i
kzzKxx −− −+= (14)
T
kzzk
i
kk
ukf
i
kKPKPP kk ~~
)(
1|
)(
ˆ−= (15)
where Kk is the Kalman gain, calculated with
equation 1
~~
=kkkk zzzxk PPK,
=
−−−− −−= a
kk
n
j
Ti
kk
i
kkj
i
kk
i
kkj
c
jzz zZzZWP
2
0
)(
1|
)(
1|,
)(
1|
)(
1|,
)(
~~ ]][[ (16)
=
−−−− −−= a
kk
n
j
Ti
kk
i
kkj
i
kk
i
kkj
c
jzx zZxWP
2
0
)(
1|
)(
1|,
)(
1|
)(
1|,
)(
~
~]][[
χ
(17)
Here, we have obtained state and corresponding
covariance estimates through UKF-update process.
Consequently, we use the EKF to do the update process
with the pre-computed state estimate ukf
i
k
x)( as input.
First, predict the state and covariance using the
following,
)()( )()(
1
)(
1| ukf
i
k
i
k
ekf
i
kk xfxfx == −− (18)
)()()()(
1
)()(
1|
iT
kk
i
k
iT
k
i
k
i
k
ekf
i
kk GQGFPFP += −− (19)
The Kalman gain can be calculated,
1)()(
1|
)()()()()(
1|][
−− += iT
k
ekf
i
kk
i
k
iT
kk
i
k
iT
k
ekf
i
kkk HPHURUHPK
(20)
So, the updated state and covariance estimates at time
k are,
ekf
i
kk
i
kk
ekf
i
kk
ekf
i
kPHKPP )(
1|
)()(
1|
)(
ˆ−−−= (21)
Algorithm 1: Generic Particle Filter
Step 1. Initialization. k=0
(1) FOR i=0, …, N
Draw the states i
x0 from the prior )( 0
xp ;
END FOR
Step 2. FOR k=1, 2, …
(1) FOR i=1,…,N
Draw ),|(~ 1k
i
k
i
k
i
kzxxqx ;
Assign the particle a weight according to
Equ.(8);
END FOR
(2) FOR i=1,…,N
Normalize the weights=
=N
j
j
k
i
k
i
kwww 1
/;
END FOR
(3) Resample
Eliminate the samples with low importance
weights and multiply the samples with high
importance weights, to obtain N random
sample i
k
x:0 which are approximately
distributed according to)|( :1:0kk zxp;
FOR i=1, …, N, leti
k
w=1/N, END FOR
END FOR
Step 3. k=k+1, goto Step2 or end executing.
PARTICLE FILTERING WITH MULTI PROPOSAL DISTRIBUTIONS 25
Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103
))((
ˆ)(
1|
1)()()(
1|
)(
ekf
i
kkkk
iT
k
ekf
i
k
ekf
i
kk
ekf
i
kxhzRHPxx
−+= (22)
where Q is process noise covariance and R is
measurement noise covariance. F)(i
k, G)(i
kand H)(i
k,
U)( i
kare the Jacobians of the process and measurement
models, respectively. The estimatesekf
i
k
x)( and ukf
i
k
P)(
ˆare
the estimates to be computed at time k.
For the other 1-c percent of the particles, we can
directly compute the state estimates using the state
transition model (2),
)( )(
1
)(
1|
i
k
i
kk xfx−− = (23)
The MPD-PF algorithm can be shown as in Algorithm
2.
Algorithm 2: The MPD-PF algorithm
Step 1. Initialization: k=0
(1) FOR i=1…N, draw the particles )(
0
i
x from the
prior p(x0) and set:
)(]))([(
]0,0,)[(][
]))([(
)(
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
)(
0
RQPdiagxxxxEP
xxEx
xxxxEP
xEx
iTaiaiaiaiai
TTiaiai
Tiiiii
ii
=−−=
==
−−=
=
ENDFOR
Step 2. FOR k=1,2,…
(1). FOR i=1,…,cN,
- Update the particles using the UKF, and obtain the
state estimate ukf
i
k
x)( and covariance
estimate ukf
i
k
P)(
ˆ.
- Using the EKF to do the update process:
Let)(
1
i
k
x=ukf
i
k
x)( , and compute one-step-ahead
estimates of the state and the covariance with
the equations (18-19).
Compute the updated state and covariance
estimates with the equations (21-22).
Let ukf
i
k
i
k
ekf
i
k
i
kPPxx )()()()( ˆˆ
,== .
- Draw)
ˆ
,(),|(~
ˆ)()(
:1
)(
1:0
)()( i
k
i
kk
i
k
i
k
i
kPxNzxxqx =
//c percent particles are drawn here.
- Assign the particle a weight, i
k
waccording to Equ.
(8).
ENDFOR
(2). FOR i=cN+1,…,N
- Directly compute the state estimate using Equ.
(23).
- Draw)|(~
ˆ)(
1
)(
1|
)( i
k
i
kk
i
kxxpx −−
//1-c percent particles are drawn here
- Assign the particle a weight.
(3). FOR i=1,…,N, Normalize the weights,
=
=Nj
j
k
i
k
i
kwww :1
/
ENDFOR
(4). RESAMPLE:
Eliminate the samples with low importance
weights and multiply the samples with high
importance weights, to obtain N random
samples i
k
x:0 approximately distributed
according to the posterior PDF p(x0:k|z1:k).
FOR i=1,…,N let i
k
w=1/N. ENDFOR
Step 3. k=k+1, goto Step2 or end executing.
4. Experimental Results
In this section, we present the experimental results of
the MPD-PF algorithm and compare the performance of
several existing particle filtering algorithms. The system
and the measurement models used in the experiment are:
[
]
11
5.0)1(04.0sin1−−
+
+−
+
=
kkk vxkx
π
(24)
30
30
25.0
2.0 2
>
+−
+
=k
k
ux
ux
z
kk
kk
k (25)
where vk denotes a Gamma random variable and )2,3(
a
ζ
modeling the process noise, and the measurement noise uk
is drawn from a Gaussian distribution N(0,0.0001). 200
particles are used and the process is repeated 100 times
for time-steps k=1,..,60. The output of the algorithm is the
mean of samples set which can be computed using (22):
=
=N
j
j
kk x
N
x
1
1
ˆ (26)
The Mean Square Errors (MSE) of each run is defined
as
2/1
1
2
)
ˆ
(
1
−=
=
T
k
kk xx
T
MSE (27)
The program run on a computer with CPU: Celeron
2.66GHz and Memory: 1GB.
If c is set to be 0.3, Figure 1 shows the comparison of
the estimates to the system state generated from a single
run of different particle filters. It is shown that the
estimates of the PF and the EKPF bias the true state very
large at some time steps, but the UPF and the MPD-PF
can improve the performance.
Figure 2 shows the comparison of the Root MSE of
different particle filters generated over 100 runs. It is
clearly shown that the MPD-PF gives the best
performance compared to other particle filters, which also
26 F.S. WANG ET AL.
Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103
can be seen in Table 1. Table 2 gives the average time of
the UPF and the MPD-PF spent after 100 independent
runs. The UPF spent longer running-time – 26.8 seconds,
while the MPD-PF spent much shorter – 17.6 seconds. So,
from Table I and II, we can clearly see that the MPD-PF
gives us much higher accuracy with lower time cost,
when the parameter c is set to be 0.3.
010 20 30 40 50 60
-5
0
5
10
15
20
Time
E(x
t
)
Estimated state and True state
Noisy observations
True x
PF estimate
EKPF estimate
UPF estimate
MPD-PF estimate
Figure 1. Estimates generated by different particle filters
Table 1. The means and the variances of the MSE over 100
independent runs (c=0. 3).
MSE
Algorithm
Mean variance
PF 0.21374 0.052091
EKPF 0.28551 0.02258
UPF 0.054599 0.004701
MPD-PF 0.016846 5.8999e-006
Figure 3 shows changing trend of the MSE of different
particle filters, while the value of parameter c is
increasing. From this figure, we can see that MPD-PF
gives the best performance whatever the value of c. As to
executing time of the particle filters, Figure 4 gives the
changing trend of the executing time of the particle filters,
from which we can see that, when the value of parameter
c is turning bigger, the time cost of MPD-PF is increasing
at the same time. At the point of c=0.8, it exceeds the
UPF. For users with different requirements, they can
flexibly adjust the value of parameter c according to their
practical needs.
5. Conclusion
In this paper, multi-proposal-distribution based
particle filter is introduced. It first takes a divide-conquer
strategy, which draws the required particles using
different proposals, and can give a better performance
than several particle filters. The simulation results show
that it can give much higher accuracy than the other
particle filters, especially that, it can save a lot of
executing time. With proper choice of c, the MPD-PF can
supply us a fast and efficient way in dealing with some
nonlinear filtering problems in real world applications,
such as signal processing problems and nonlinear
situations raised in wireless communications, etc. For
people with different practical requirements, they can
flexibly adjust the value of parameter c in order to obtain
ideal results.
Table 2. The average time of UPF and MPD-PF used in the
experiment
Algorithm Time (seconds)
UPF 26.8
MPD-PF 16.62
010 20 30 40 50 60
0
0. 2
0. 4
0. 6
0. 8
1
1. 2
1. 4
Time
Root MS
PF
EKPF
UPF
MPD-PF
Figure 2. Root MSE of different particle filters after 100 independent runs (c=0.3).
PARTICLE FILTERING WITH MULTI PROPOSAL DISTRIBUTIONS 27
Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103
0.10.2 0.3 0.4 0.50.6 0.7 0.8 0.91
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
Values of parameter c
Root MSE of Different Particle Filters
PF EKPF MPD-PF UPF
Figure 3. Changing trendline of MSE
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
5
10
15
20
25
30
value of parameter c
Average time of different PFs over 100 runs
PF
EKPF
UPF
PF-MPD
Figure 4. Changing trendline of execution time.
6. References
[1] J. H. Kotecha and P. M. Djuric, “Gaussian Particle
Filtering”, IEEE Transactions on signal processing.
vol.51, no.10, 2003, pp. 2592-2601.
[2] N.J. Gordon, D.J. Salmond, A.F.M. Smith, “Novel
approach to nonlinear/non-Gaussian Bayesian state
estimation”, IEE. proceedings-F, vol.140, no.2, 1993,
pp.107-113
[3] Rui Y, Chen Y., “Better proposal distributions:
Object tracking using unscented particle filter”,
IEEE Conf. on Computer Vision and Pattern
Recognition, 2001, pp. 786793.
[4] H. Kamel, W. Badawy. “Adaptive equalization of a
communication channel in a non-Gaussian noise
environment”, Proc. of 3rd International IEEE-
NEWCAS Conference, Jun. 19-22 2005. pp.395-398
[5] Y.M. Liang, H.W. Luo, X.X. Zhao, H.B. Zhang,
C.G. Y. “Nonlinear Channel Estimation Based on
Particle Filtering for MIMO-OFDM Systems”, Proc.
of International Conference on Communications,
Circuits and Systems, Vol. 1. Jun. 2006. pp.347-351.
[6] S. Haykin, K. Huber, Zhe Chen. “Bayesian
Sequential State Estimation for MIMO Wireless
Communications”. Proc. of the IEEE. Vol. 92 Issue
3. Mar. 2004. pp.439-454.
[7] Anis Ziadi, Gerard Salut. “Non-overlapping
deterministic Gaussian particles in maximum
likelihood non-linear filtering- phase tracking
application”. Proc. of International Symposium on
Intelligent Signal Processing and Communication
Systems. 2005. pp. 645-648
[8] FANG Zheng, TONG Guo-Feng, XU Xin-He, “A
Robust and Efficient Algorithm for Mobile Robot
Localization”. ACTA Automatic Sinica, Vol. 33,
NO. 1. Jan. 2007. pp. 48-53.
[9] Cody Kwok, Dieter Fox, and Marina Meila, “Real-
Time Particle Filters”, Proceedings of the IEEE,
vol.92, no. 3, Mar. 2004, pp.469-484.
[10] Christian Plagemann, Dieter Fox, Wolfram Burgard,
“Efficient Failure Detection on Mobile Robots
Using Particle Filters with Gaussian Process
Proposals”, proceedings of International Joint
Conference on Artificial Intelligence, Hyderabad,
India. Jan. 6-12, 2007. pp. 2185-2190.
[11] F. Gustafsson, F. Gunnarsson, N. Bergman, U.
Forssell, J. Jansson, R. Karlsson, J. Nordlund,
“Particle filters for positioning, navigation, and
tracking”, IEEE Transactions on Signal Processing,
2002, pp.425437.
[12] Rudolph van der Merwe, Arnaud Doucet, Nando de
Freitas, Eric Wan, “The unscented particle filter”,
Technical report. Cambridge University.
Engineering Department. 2000.
[13] Greg Welch, Gary Bishop, “An Introduction to the
Kalman Filter”, Technical Report, TR 95-041,
University of North Carolina at Chapel Hill, 2004.
[14] Simon J. Julier and Jeffrey K. Uhlmann, “Unscented
Filtering and Nonlinear Estimation”, proceedings of
the IEEE, vol. 92. no. 3, 2004, pp.401-422.
[15] Eric A. Wan and Rudolph van der Merwe, “The
Unscented Kalman Filter for Nonlinear Estimation”,
proceedings of ASSPCC, 2000, pp.153-158.
[16] Michael Isard, Andrew Blake, “Condensation –
conditional density propagation for visual tracking”,
International Journal of Computer Vision, 1998. pp.
5~28
[17] M. Sanjeev Arulampalam, Simon Maskell, N.
Gordon and T. Clapp, “A tutorial on particle filters
for On-line Nonlinear/Non-Gaussian Bayesian
Tracking.” IEEE Transactions on signal processing,
vol.50, no.2, 2002, pp.174-188.
28 F.S. WANG ET AL.
Copyright © 2008 SciRes. I. J. Communications, Network and System Sciences. 2008; 1:1-103
[18] Arnaud Doucet, “On Sequential Simulation-Based
Methods for Bayesian Filtering”, Technical report.
Signal Processing Group, Department of
Engineering, University of Cambridge, 1998.
[19] Tanya Bertozzi, Didier Le Ruyet, Gilles Rigal and
Han Vu-Thien, “On Particle Filtering for Digital
Communications”, Proc. of 4th IEEE Workshop on
Signal Processing Advances in Wireless
Communications, 2003, pp570-574.