The research paper published by IJSER journal is about Adaptive Particle Filter Approach To Approximate Particle Degeneracy 1

ISSN 2229-5518

Adaptive Particle Filter Approach to Approximate

Particle Degeneracy

J.Joseph Ignatious ,A.UmaMageswari, S.Abraham Lincon.

Abstract –– The main problem of particle filter in nonlinear state estimation is the particle degeneracy. It can be overcome by Resa mpling operation. But Resampling operation leads to the problem of sample impoverishment. Therfoer an algorithm named Variance red uction technique is proposed to solve sample impoverishment and degeneration problem. It reduces the variance of the part icle weights by selecting an exponential fading factor and this factor can be chosen adaptively and iteratively in terms of the effective particle number. Many improved particle filter algorithms were proposed to solve the degeneracy problem which are seemed to be complex. In this paper an algorithm is presented to show that the idea of Variance reduction technique is feasible to propose a new adaptive filter ing algorithm.

Keywords— Particle filter, Adaptive Particle filter , particle degeneracy, sample Impoverishment, Adaptive Algorithm.

——————————  ——————————

1.INTRODUCTION

Particle filter (PF) is a Monte Carlo estimation algorithm suitable for the state estimation of nonlinear and/or non-Gaussian systems by constructing the posterior probability density function via a number of weighted particles. It is widely used in target tracking, signal processing, image processing and so on.[1-2]. However, PF may confront the particle degeneracy. The resampling operation solves the degeneration of the particle set to some extent, but it leads to the problem of sample impoverishment. Therefore, how to deal with the degeneration of the particle
set effectively is a crucial problem in PF design. For many
years, much attention has been paid to solve the issue of
particle degeneration and sample impoverishment. Some
novel techniques were adopted to solve this problem, and many improved algorithms of PF were proposed which included regularized particle filter[3], auxiliary particle filters, auxiliary extended and auxiliary unscented Kalman particle filters [4], genetic particle filter (GPF)[5], risk sensitive particle filters (RSPF) [6], and so on.

J.Joseph Ignatious, Research Scholar,

Faculty of Engineering, Annamalai University, Chidambaram,TamilNadu,India.

E-mail: jji_02@yahoo.co.in

A.UmaMageswary, Research Scholar,

Faculty of Engineering, Annamalai University,

Chidambaram,TamilNadu,India.

E-mail: uma.sathya123@yahoo.co.in

S.Abraham Lincon, Professor, Dept of E & I, Faculty of Engineering, Annamalai University, Chidambaram,TamilNadu,India.

To overcome the sample impoverishment after resampling step, the fission bootstrap PF (FBPF)[7] algorithm was proposed , in which the preprocessing included weights sorting, particle reproducing by fission and weights normalizing was inserted before the original resampling step as soon as the particle set degenerates severely. However, the problems of weights allocation and the number of fissional particles were not solved well.Annealed particle filter proposed restrained the degeneration by introducing an annealing factor but the choice of this factor is somewhat complex.
In order to solve the degeneracy of the particle set, this paper proposes an adaptive PF (APF) algorithm via variance reduction technique.After setting a threshold of effective particle number and the reduction rate, the fading factor was chosen by the variance of importance weights recursively and adaptively. A numerical example was given to show that the proposed APF in this paper has better estimation accuracy compared with generic particle filter sampling importanceof resampling (PF-SIR), generic particle filter (GPF)[8]. In this paper , section2 deals with the particle filter and its estimation, section 3 deals with the adaptive particle filter and its algorithm, section 4 deals with the numerical example based on univariate non stationary growth model, section 5 deals about the simulation results by simulating the UNGM[9] model equation and last chapter deals with the conclusion.
Through this papar we use the following notaions:

K:time step

Wk :process noise

Vk :observation noise

Xk: State vector

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about Adaptive Particle Filter Approach To Approximate Particle Degeneracy 2

ISSN 2229-5518

Yk:Observation vector X(n):Input signal D(n):Desired signal E(n): Error signal

V(n): Interfering noise

2.PARTICLE FILTER

The particle filters are also known as Sequential Monte Carlo methods (SMC), are sophisticated model estimation techniques based on simulation. The particle filter aims to estimate the sequence of hidden parameters, xk for k = 0,1,2,3,…, based only on the observed data yk for k = 0,1,2,3,…. All Bayesian estimates of xk follow from the posterior distribution p(xk | y0,y1,…,yk). In contrast, the MCMC or importance sampling approach would model the full posterior p(x0,x1,…,xk | y0,y1,…,yk).

Particle methods assume and the observations can be modeled in this form: is a first order Markov process such that and with an initial distribution .


The observations are conditionally independent provided that are known. In other words, each only depends on

One example from this scenario is (1) (2)
where both and are mutually independent and identically distributed sequences with known probability density functions and and are known functions. These two equations can be viewed as state space equations and look similar to the state space equations for the Kalman filter. If the functions and are linear, and if both and are Gaussian, the Kalman filter finds the exact Bayesian filtering distribution. If not, Kalman filter based methods are a first-order approximation (EKF) or a second- order approximation (UKF in general, but if probability distribution is Gaussian a third-order approximation is possible). Particle filters are also an approximation, but with enough particles they can be much more accurate.
In the implementation of particle filters, there are three important operations:
1. Generation of particles (sample step),
2. Computation of the particle weights (importance step), and
3. Resampling.
The first two steps form the particle filter called Sequential Importance Sampling (SIS) filter. The filter that performs all three operations is called Sample Importance Resampling Filter(SIRF).
The particle filter is a useful tool to perform dynamic state estimation via Bayesian inference. It provides great efficiency and extreme flexibility to approximate any functional nonlinearity. The key idea is to use samples, also called particles, to represent the posterior distribution of the state given a sequence of sensor measurements. As new information arrives, these particles are constantly re-allocated to update the estimation of the state of the system. The efficiency and accuracy of the particle filter depends mainly on two key factors: the number of particles used to estimate the posterior distribution and the propagation function used to re-allocate these particles at each iteration. The standard implementation of the filter specifies both factors beforehand and keeps them fixed during the entire operation of the filter.

3.ADAPTIVE PARTICLE FILTER

An adaptive filter is a filter that self-adjusts its transfer function. The optimization algorithms is so complex that adaptive filters are used as digital filters. This is required for some applications where parameters of the desired processing operation are not known in advance. The adaptive filter uses feedback in the form of an error signal. The particle filter has emerged as a useful tool for problems requiring dynamic state estimation. The efficiency and accuracy of the filter depend mostly on the number of particles used in the estimation and on the propagation function used to re-allocate these particles at each iteration. Both features are specified beforehand and are kept fixed in the regular implementation of the filter. In practice this may be highly inappropriate since it ignores errors in the models and the varying dynamics of the processes.
This work presents a self adaptive version of the particle filter that uses statistical methods to adapt the number of particles and the propagation function at each iteration. Furthermore, our method presents similar computational load than the standard particle filter.
In this paper, we present a self adaptive particle filter that shown in Figure 1 uses statistical methods to select an appropriate number of particles and a suitable propagation function at each iteration. In this,after setting a threshold of

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about Adaptive Particle Filter Approach To Approximate Particle Degeneracy 3

ISSN 2229-5518

effective particle number and the reduction rate ,the fading factor was chosen by the variance of importance weights recursively and adaptively.
Variance reduction is always realized by introducing the correlation into the sample set. Here we adopt an idea of variance reduction to achieve the aim of reducing the weights variance of particles

Figure 1. Adaptive filter structure

The input signal x(n) is the sum of a desired signal d(n) and interfering noise v(n)

(3) The variable filter has a Finite Impulse Response

(FIR) structure. For such structures the impulse response is
equal to the filter coefficients. The coefficients for a filter of order are defined as
. (4)
The error signal or cost function is the difference between the desired and the estimated signal

(8)

Where the parameter is a correction factor for the filter coefficients. The adaptive algorithm generates this correction factor based on the input and error signal x(n)

3.1Adaptive Algorithm

To alleviate the degeneration on particle set, it seems necessary to reduce the variance of weights of prior particles.

Variance reduction of weights

Variance reduction is always realized by introducing the correlation into sample set. For PF, the principles of reducing the weights variance should be as follows
1) For the particle having relatively high weights, we decrease their weights.
2) For the particle having relatively low weights, we increase their weights.
3) Keep the original order of all particle weights remaining unchanged, i.e. keep a higher weight to be higher and a lower weight to be lower.
The above proposed theorem subsequently provides powerful evidence that a small (larger than 0 and over smaller than 1) exponent factor to all weights can decrease the weights variance of particles, i.e., increase the effective particle number. And,the smaller the exponent factor is the larger the effective particle number.

Step 1:

Select the parameter that determines the rate of variance reduction at each time k and set a threshold Nthr for effective particle number, let t=n-1,wk0=wk

Step 2:

(5)

The variable filter estimates the desired signal by convolving the input signal with the impulse response. In vector notation this is expressed as

(6) Where

(7)

is an input signal vector. Moreover, the variable filter updates the filter coefficients at every time instant

Step 3: Step 4:

Step 5:

Compute the effective particle number Neff
While Neff<Nthrα=t/n,wk=(wk0)α,t=t-1
Normalize the weight for each particle wk-i=wki/∑wkj
Estimate the state
Xk =Σ wk–ixki

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about Adaptive Particle Filter Approach To Approximate Particle Degeneracy 4

ISSN 2229-5518

Step 6:

Step 7:

Estimate the covariance Pk =Σ(xik − xk) ˜ wik(xik − xk)T

Draw new particles xki~N(xki,pk),and set {wk-i=1/N}N

4.UNIVARIATE NON-STATIONARY GROWTH MODEL AND RESULTS

To illustrate some of the advantages of APF over PF
,Let us now consider an example[10-11], in which we estimate
a model called Univariate Nonstationary Growth Model
(UNGM), which is previously used as benchmark .what
makes this model particularly interesting in this case is that its
highly nonlinear and bimodal, so it is really challenging for traditional filtering techniques. The dynamic state space model for UNGM can be written as

(9) The cosine term in the state transition equation simulates the effect of time-varying noise. From Eq no.9 ,we choose α=0.5,β=25,γ=8.

For N=100 Particles,the root mean square error(RMSE) curves of the estimated results are 11.1394(particle filter) and
2.8254(Adaptive particle filter) Fig. 2 and Table 1 shows that APF has higher accuracy than particle filter in the estimation of this nonlinear system with non-Gaussian noise.

(a)

Fig.2. (a) Estimation of Adaptive pdf.

(b) Estimation of Particle filter.

(c) Estimation of Adaptive Particle filter. (d) Resample of Adaptive Particle filter.

(b)

(c)

(d)

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about Adaptive Particle Filter Approach To Approximate Particle Degeneracy 5

ISSN 2229-5518

By simulating the state transition equation of adaptive particle filter based on univariate non-stationary growth model,we obtain the results which is shown in Figure2 and the RMSE value of particle filter and adaptive particle filter are shown in the Table 1
Table 1 RMSE Performance of Two Algorithms

[8] N. J. Gordon, D. J. Salmond, and A. F. M. Smith, “Novel approach to nonlinear/non-Gaussian Bayesian state estimation,”IEE Proceedings F Radar and Signal Processing, vol. 140, no. 2, pp. 107–113, 1993.

[9] M. S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, “A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking,” IEEE Transactions on Signal Processing, vol. 50, no. 2, pp.

174–188, 2002.

5. CONCLUSION

In this paper, we have developed an Adaptive particle filter that overcomes the major problem of particle degeneracy. Here we have adopted the idea of resampling operation to overcome the problem of particle degeneracy but it leads to the problem of sample impoverishment. So we proposed an algorithm based on variance reduction technique which reduces the variance of the particles. It overcomes both the problem and produce the particle with more accuracy compared to the prior methods.More experiments are necessary in order to validate the algorithm. Further improvements of the algorithm are necessary to reduce error completely.

REFERENCES

[1].Gordon N J, Salmond D J, Smith A F M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings F: Radar and Signal Processing, 1993, 140(2): 107-113

[2] Giremus A, Tourneret J Y, Djuric P M. An improved regulaized particle filter for GPS/INS integration. In: Proceedings of the 6th I nternational Workshop on SignalProcessing Advances in Wireless Communications. New York, USA: IEEE 2005. 1013-1017

[3] D. B. Ward, E. A. Lehmann, and R. C. Williamson, “Particle

filtering algorithms for tracking an acoustic source in a reverberant

environment,” IEEE Transactions on Speech and Audio

Processing, vol. 11, no. 6, pp. 826–836, 2003.

[4] Pitt M, Shephard N. Filtering via simulation: auxiliary particle fi lters.

Journal of the American Statistical Association,1999, 94(446): 590−599

[5] Higuchi T. Monte Carlo filtering using the genetic algorithm operators.

Journal of Statistical Computation and Simulation , 1997, 59(1): 1−23

[6] Orguner U, Gustafsson F. Risk sensitive particle filters for mitigating sample impoverishment. IEEE Transactions on Signal Processing, 2008,

56(10): 5001−5012

[7] Cheng S Y, Zhang J Y. Fission bootstrap particle filtering. Acta Electronica

Sinica, 2008, 36(3): 500−504

IJSER © 2012

http://www.ijser.org