Advanced
Performance Degradation Due to Particle Impoverishment in Particle Filtering
Performance Degradation Due to Particle Impoverishment in Particle Filtering
Journal of Electrical Engineering and Technology. 2014. Nov, 9(6): 2107-2113
Copyright © 2014, The Korean Institute of Electrical Engineers
  • Received : March 10, 2014
  • Accepted : June 09, 2014
  • Published : November 01, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Jaechan Lim
Corresponding Author: Department of Creative IT Engineering and Future IT Innovation Laboratory, Pohang University of Science and Technology, Korea. (jclim@postech.ac.kr)

Abstract
Particle filtering (PF) has shown its outperforming results compared to that of classical Kalman filtering (KF), particularly for highly nonlinear problems. However, PF may not be universally superior to the extended KF (EKF) although the case (i.e. an example that the EKF outperforms PF) is seldom reported in the literature. Particularly, PF approaches show degraded performance for problems where the state noise is very small or zero. This is because particles become identical within a few iterations, which is so called particle impoverishment (PI) phenomenon; consequently, no matter how many particles are employed, we do not have particle diversity regardless of if the impoverished particle is close to the true state value or not. In this paper, we investigate this PI phenomenon, and show an example problem where a classical KF approach outperforms PF approaches in terms of mean squared error (MSE) criterion. Furthermore, we compare the processing speed of the EKF and PF approaches, and show the better speed performance of classical EKF approaches. Therefore, PF approaches may not be always better option than the classical EKF for nonlinear problems. Specifically, we show the outperforming result of unscented Kalman filter compared to that of PF approaches (which are shown in Fig. 7(c) for processing speed performance, and Fig. 6 for MSE performance in the paper).
Keywords
1. Introduction
In signal processing disciplines, there are many variables of interest to be estimated. Usually, a variable is estimated based on a measurement (observation) which is a function of the variable of interest. For instance, the “radio detection and ranging (RADAR)” dish (antenna) transmits radio wave pulses that bounce off any objects in their path. The range, direction, altitude, and the speed of objects are determined based on the returned signal (measurement). Conventionally, the variable of interest is considered as a deterministic value rather than a random value. In this case, a classical maximum likelihood estimator (MLE) is a powerful approach.
On the other hand, Bayesian approaches estimate a variable in a probabilistic manner such as minimum mean squared error criterion which computes the expected value of the variable with respect to the posterior function. Particularly, if a variable of interest is varying with time or space as a random process, the Kalman filter (KF) which is a Bayesian approach might be the most powerful and popular method.
The dynamic state system that describes the hidden state x and observed measurement y with zero mean and additive noise processes of u and w at time step k are expressed as follows:
PPT Slide
Lager Image
PPT Slide
Lager Image
where boldface denotes a vector representation, g (⋅) and h (⋅) are the given state transition function and the measurement function, respectively, which are possibly nonlinear fuctions. Based on this system model, we can estimate the time-varying state xk sequentially by using the measurement yk at each time step via dynamic filters, e.g. the Kalman filter, particle filter, and their variants. The minimum mean squared error (MMSE) estimate for the above problem can be obtained as follows:
PPT Slide
Lager Image
where “1 : k” indicates the time indices from 1 to k, ^ denotes an estimated version, and p ( x 0:k | y 1:k ) is the posterior density. In the particular case that: both g (⋅) and h (⋅) are linear functions; and uk and wk are Gaussian distributed, the Kalman filter (KF) is the optimal MMSE estimator [1] . The KF estimates the state sequentially in a closed form as follows:
PPT Slide
Lager Image
where Κ k is the Kalman gain that is computed by the algorithm at each time step, and
PPT Slide
Lager Image
In general cases, i.e. other than the linear and Gaussian case, there exist a number of sub-optimal approaches such as particle filtering (PF) [2] . The Kalman filter also can be applied as a sub-optimal approach to nonlinear model by extending it using Taylor series (in this case, still Gaussian noise is assumed). Readers can be referred to [3 , 4] for more details about Kalman filtering and extended Kalman filtering. Particle filtering generates random particles (which represent the possible states) according to a proposal density (or importance function) based on the posterior function. The weight of each particle is computed based on the relation of the proposal density to the posterior function, and normalized. Therefore, the posterior function is approximated by particles as follows:
PPT Slide
Lager Image
where ip is the particle index, N is the number of employed particles,
PPT Slide
Lager Image
is the weight of the particle ip at the time step k , and δ (⋅) denotes the Dirac delta function that has the following property.
PPT Slide
Lager Image
The estimate
PPT Slide
Lager Image
is obtained in two criteria: i.e. MMSE and maximum a posteriori (MAP) estimates as follows:
PPT Slide
Lager Image
PPT Slide
Lager Image
However, standard PF such as sequential importance resampling (SIR) PF has a drawback when the state system noise is very small or zero because particle impoverishment (PI) phenomenon occurs. PI is caused by the resampling process which results in the particles that have high weights statistically selected many times; consequently, resultant particles contain many repeated particles, and hance all particles may turn into identical particles within a few iterations [2] . PI phenomenon degrades the performance since the left identical particles do not converge to the true value, and the problem may not be eliminated unless sufficiently many particles are employed. Ironically, resampling process is employed to cope with the degeneracy problem that the variance of particles becomes smaller with iterations; consequently, diversity of the particles disappears, which results in the degraded estimating performance of PF approaches.
In this paper, we investigate this PI problem by providing an example problem where the PI is observed. In the literature, it is usually reported that PF shows outperforming result compared to that of classical Kalman filtering approaches in various problems whereas the opposite result is seldom reported. Therefore, we provide this rare case in which PF approaches are well-outperformed by conventional Kalman filtering approaches.
2. CFO Estimation In OFDM Systems
In data communication systems, by employing orthogonal frequency division multiplexing (OFDM) scheme, we can eliminate inter-symbol-interference problem based on additionally inserted prefix codes. On the other hand, this system has unavoidable defect of inter-carrier interference problem caused by carrier frequency offset (CFO). Therefore, estimating CFO is important in OFDM systems.
The binary bits are mapped to data symbols ( A ( r ) ) on the complex signal constellation space. Grouped symbols (i.e. an OFDM symbol) are modulated onto sub-carriers in the form of inverse fast Fourier transform (IFFT) as follows:
PPT Slide
Lager Image
where A ( r ) is a data symbol (for example, 1+ j , −1+ j , −1− j and in the case of quadrature phase shift keying), and K is the number of sub-carriers. The cyclic prefix is added up to the signal to mitigate the intersymbol interference, and is removed at the receiver. Then the received signal (measurement) is expressed in the time domain as follows:
PPT Slide
Lager Image
where Ψ is a normalized CFO (i.e., relative offset from a carrier frequency, therefor, its maximum value is 1); fl ( l = 0, 1, … , L −1) is the L -tap channel impulse response; and wk is unknown additive noise. We want to estimate Ψ based on the received signals.
The corresponding dynamic state system and the measurement equations for the problem can be modeled as follows:
PPT Slide
Lager Image
PPT Slide
Lager Image
where we can assume CFO (Ψ) is a constant within the data frame (i.e. k is from 0 to K − 1). In this example, the observation function h (⋅) is time-varying, i.e hk (⋅) . Then, from (9), we obtain
PPT Slide
Lager Image
We assume known preamble symbols “ A ( r )”; we also assume the channel impulse response “ f l ” is given. We apply approaches to this problem under above noted noise scenario.
3. Classical Approaches and Particle Filtering
The Kalman filter has been successfully employed for numerous applications since its invention [1] . Its extended version, i.e. extended Kalman filter (EKF) is also effectively employed for applications in the cases of nonlinear models [5 , 6] . The first order Taylor expansion is employed for approximating nonlinearity into a linear form, which may result in its degraded tracking performance because the rest of terms are ignored beyond the first term of the series.
Unscented Kalman filter (UKF) is a variant of the EKF, and it was developed to obtain improved estimating performance beyond the EKF. The so called “sigma points” are employed that represent the exact mean and the variance of random states based on the state noise process. The unscented transformation of sigma points is performed to represent the nonlinearity of the state and / or measurement functions. Although UKF requires processing time which is longer than that of the EKF, we can obtain improved and more stable tracking performance compared to that of the EKF. Details of performance will be presented shortly in the computer simulation section.
We consider sequential importance resampling (SIR) particle filter (SIR-PF) as a standard PF (SPF) approach. SIR-PF employs the prior density as the proposal density; therefore, new particles are generated as follows:
PPT Slide
Lager Image
And, then the weight is computed based on the likelihood function for each particle. The estimate is obtained by selecting either MMSE or MAP criterion as shown in (6) and (7). Therefore, SIR-PF is the simplest PF in all its variants while the optimal estimating performance is not guaranteed. The resmapling process is applied every iteration in SIRPF, which results in the likelihood function as the weight of particles.
Particle filtering is modified to resolve the particle impoverishment problem, and it is known as regularized particle filter (RPF). RPF employs a kernel density which perturbs the state of a particle to achieve the diversity of the states. Specifically, the posterior density is approximated as follows in RPF.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the rescaled kernel density for any kernel bandwidth κ > 0 ,
PPT Slide
Lager Image
is the normalized weight, ip is the particle index, N is the number of particles, and nx is the dimension of the state parameter x (i.e., Ψ in this paper), respectively. The optimal choice of the kernel is the Epanechnikov kernel; however, it can be replaced by the Gaussian kernel [7] . Then, the associated optimal bandwidth is
PPT Slide
Lager Image
Gaussian particle filter is another variant of particle filtering algorithm, and resampling step is not required in this algorithm. Therefore, its computational complexity is almost the half that of sequential importance resampling (SIR) particle filtering which resample particles every iteration [8] . GPF recursively updates only the mean and the variance of the particles. The step of generating
PPT Slide
Lager Image
is omitted in the algorithm because CFO is assumed to be a constant during an OFDM symbol period, consequently, it would generate the identical particle that is effortless.
Unscented particle filter (UPF) is another PF variant and was developed inspired by UKF [9] . Each particle has a certain number of sigma points to increase the diversity of the particle; nonetheless, the computational complexity is highly increased while the performance is marginally improved.
4. Computer Simulations
We consider a single antenna, 64 sub-carrier OFDM systems which is the minimum FFT size in LTE-advanced downlink; and, the quadrature phase shift keying scheme is employed for MATLAB simulations. Various additive Gaussian noise power level is introduced in the measurement equation for various levels of signal to noise ratio (SNR), and 1; 000 times of simulations are run for mean squared error (MSE) performance assessment. MSE is computed in the following way.
PPT Slide
Lager Image
where M is the number of simulations, iM denotes the simulation index, Ψ is the true CFO value, and
PPT Slide
Lager Image
is the estimate at time step K (the last one) in the iM -th simulation. The processing time for each approach is computed by summing up the totally required time over M simulations during the MATLAB simulations. And then, the average time is obtained over a number of Eb / N 0 values, where Eb is the bit energy and N 0 / 2 is the noise power spectra density of the measurement. Normalized CFO is randomly generated from −0.9 to 0.9. We refer to this value (i.e. 0.9) as the random offset range (ROR). Therefore, it is assumed that proper symbol timing synchronization precedes the CFO estimation such that CFO is confined within the ROR.
In Fig. 1 , we showed a realization of tracking the CFO by PF approaches by employing only ten particles in addition to EKF tracking. Except for cost-reference PF (CRPF) [10] , all PF approaches seem to show PI problem (at a certain point, the estimated value maintains the same value till the end of the tracking, i.e. a straight line) including regularized PF. Gaussian particle filter seems to show PI problem too, but as a matter of fact, it is degeneracy problem rather than PI problem because GPF does not require the resampling process. Degeneracy of particles occurs in PF framework as time goes on, and consequently, the variance of particles becomes almost zero, which results in degraded estimating performance due to the lack of particle diversity. Ironically, resampling process was adopted to avoid the degeneracy problem in PF framework. We ran the same simulation with increased number of particles ( N = 300) because PI problem can be mitigated when highly increased number of particles is employed. PI problem of most PF approaches is significantly mitigated while SIR-PF and UPF still show the PI problem as shown in Fig. 2 . This is because both SIR-PF and UPF employ resampling process while the other PF approaches do not require standard resampling process in their algorithms.
PPT Slide
Lager Image
A realization of tracking CFO by particle filtering with 10 particles and the EKF, CFO=0.8652313, Eb / N0 =40dB. It illustrates PI of PF approaches except for CRPF and GPF.
PPT Slide
Lager Image
A realization of tracking CFO by SIR-PF and UPF with 300 particles, CFO = 0:2935746, Eb / N0 =40 dB. It illustrates PI of UPF and SIR.
We increased the particle number again from 300 to 1,000, and showed the result in Fig. 3 , where PI problem of all the PF approaches seems to be eliminated. Nonetheless, the problem has not been completely eliminated, and it affects the estimating performance of PF approaches as we will show the MSE results shortly.
PPT Slide
Lager Image
A realization of tracking CFO by particle filtering with 1, 000 particles and the EKF, CFO=0:681340, Eb / N0 = 40dB.
Fig. 4 shows the MSE performance results by particle filtering approaches. CRPF shows the best MSE performance when only 10 particles are employed as shown in Fig. 4(a) . As we can see in Figs. 4(b) - (c) , Gaussian particle filter shows the best performance if we increase the number of particles. CRPF shows the worst MSE performance while RPF shows the second best performance when 1; 000 particles are employed. Although CRPF shows the best MSE performance when only 10 particles, it cannot show the optimal performance when highly increased number of particles is employed because CRPF is applied without any statistical information of the state and the measurement equations [11 , 12] . The MSE performance of SIR-PF and UPF is better than that of CRPF, but their performance is worse than that of RPF and GPF due to the affection of the PI problem when 1,000 particles are employed as shown in Fig. 4(c) .
PPT Slide
Lager Image
MSE performance by various particle filtering approaches: (a) N = 10; (b) N = 300; (c) N = 1,000.
We showed the MSE performance result in Fig. 5 where the best PF approach, i.e. GPF and conventional Kalman filters are compared (Cramer-Rao Lower bound is also compared that is derived in the appendix) where 1,000 particles were employed for GPF. The result justifies that UKF outperforms GPF, and even the EKF outperforms GPF at Eb / N 0 levels above 5dB. We compared only GPF and UKF in Fig. 6 where UKF clearly outperforms GPF over all range of Eb / N 0 . We also provide the processing time of algorithms by MATLAB simulations in Fig. 7 where the result of the best PF approach, i.e. GPF, the EKF, and UKF are compared. It can be noted that UKF requires considerably increased processing time compared to that of the EKF. UKF requires more processing time than GPF when up to 300 particles are employed while GPF requires significantly more time than UKF when 1,000 particles are employed. Therefore, although the MSE performance of GPF approaches to that of UKF as shown in Fig. 6 , significantly more processing time is required compared to that of UKF.
PPT Slide
Lager Image
MSE performance comparison between particle filtering (GPF) and Kalman filtering (EKF and UKF).
PPT Slide
Lager Image
MSE performance comparison between Gaussian particle filter and unscented Kalman filter
PPT Slide
Lager Image
Average processing time with respect to Eb / N0 , and then summed up for all number of simulations (by MATLAB): (a) N = 10; (b) N = 300; (c) N = 1,000
5. Conclusions
In this paper, we investigated particle impoverishment problem (PI) that is a drawback of employing particle filtering (PF) approaches, particularly for problems where the state noise is very small or zero. Ironically, the PI problem results from resampling process that is adopted to tackle the degeneracy problem of particles that degrades the estimating performance of PF approaches. The PI problem also degrades performance of PF approaches because the resulting single particle cannot obtain a high quality of estimates. The PI problem can be eliminated if a sufficiently large number of particles are employed. Nonetheless, as we showed by computer simulation in this paper, the problem cannot be completely eliminated, and resultantly, PF approaches cannot show outperforming result compared to that of even classical Kalman filtering approaches. In the literature, it has been seldom reported that PF approaches are outperformed by classical Kalman filtering approaches. The importance of this paper is that we showed, investigated, and provided this rare example problem. Therefore, we justified that PF approaches do not always outperform Kalman filtering approaches although PF is known to be a superior sub-optimal method to Kalman filtering for nonlinear problems.
Acknowledgements
This research was supported by “Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education (NRF-2011-0009255)” and “the Ministry of Science, ICT and Future Planning, Korea, under the ‘IT Consilience Creative Program’ (NIPA-2014-H0201-14-1001) supervised by the National IT Industry Promotion Agency.”
BIO
Jaechan Lim received the B.S. degree in physics from Korea University, Seoul, Korea in 1996, and the M.S. and Ph.D. degrees in electrical engineering from Stony Brook University, Stony Brook, New York in 1999 and 2007, respectively. His research areas include statistical signal processing, Bayesian estimation, the Kalman filtering, particle filtering, OFDM systems, operations of wireless access network and communication systems (LTE), GPS / INS navigation system in launch vehicles, and biomedical image processing. He was with the Department of Electronic Engineering in Sogang University, Seoul, Korea as a research professor. He was with Gumi Electronics and Information Technology Research Institute, Gumi, Korea as a senior staff research engineer. He is currently with the Department of Creative IT Engineering and Future IT Innovative Laboratory in Pohang Institute of Science and Technology, Pohang, Korea as a senior staff researcher.
References
Kalman Rudolph Emil 1960 “A new approach to linear filtering and prediction problems” Transactions of the ASME-Journal of Basic Engineering 82 (Series D) 35 - 45    DOI : 10.1115/1.3662552
Arulampalam M. , Maskell Simon , Gordon Neil , Clapp Tim 2002 “A tutorial on particle filters for online nonlinear / non-Gaussian Bayesian tracking” IEEE Trans. Signal Processing 50 (2) 174 - 188    DOI : 10.1109/78.978374
Hayes Monson H. 1996 Statistical digital signal processing and modeling John wiley & sons, inc
Kay Steven M. 1993 Prentice hall signal processing series, Estimation Theory Fundamentals of statistical signal processing
Lee H. , Ra W. , Lee J. , Song Y. , Whang I. 2012 “Aerodynamic derivatives identification using a nonconservative robust Kalman filter” Journal of Electrical Engineering & Technology 7 (1) 132 - 140    DOI : 10.5370/JEET.2012.7.1.132
Sim H. , Lee J. , Lee K. 2014 “On-line parameter estimation of interior permanent magnet synchronous motor using an extended Kalman filter” Journal of Electrical Engineering & Technology 9 (2) 600 - 608    DOI : 10.5370/JEET.2014.9.2.600
Musso C. , Oudjane N. , LeGland F. , Doucet A. , de Freitas J. F. G. , Gordon N. J. 2001 Sequential Monte Carlo Methods in Practice Springer-Verlag New York “Improving regularised particle filters”
Kotecha J. H. , Djuric P. M. 2003 “Gaussian particle filtering” IEEE Transactions on Signal Processing 51 (10) 2592 - 2601    DOI : 10.1109/TSP.2003.816758
Merwe Rudolph van der 2004 Sigma-point Kalman filters for probabilistic inference in dynamic state-space models, Ph.D. thesis OGI School of Science & Engineering, Oregon Health & Science University Portland, Oregon
Lim Jaechan 2013 “A target tracking based on bearing and range measurement with unknown noise statistics” Journal of Electrical Engineering & Technology 8 (6) 1520 - 1529    DOI : 10.5370/JEET.2013.8.6.1520
Lim J. , Hong D. 2009 “Inter-carrier interference estimation in OFDM systems with unknown noise distributions,” IEEE Signal Processing Letters 16 (6) 493 - 496    DOI : 10.1109/LSP.2009.2017571