Full Text:   <2789>

Summary:  <593>

CLC number: TN713

On-line Access: 2015-11-04

Received: 2015-06-24

Revision Accepted: 2015-09-01

Crosschecked: 2015-09-10

Cited: 8

Clicked: 8781

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Tian-cheng Li

http://orcid.org/0000-0002-0499-5135

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2015 Vol.16 No.11 P.969-984

http://doi.org/10.1631/FITEE.1500199


Resampling methods for particle filtering: identical distribution, a new method, and comparable study


Author(s):  Tian-cheng Li, Gabriel Villarrubia, Shu-dong Sun, Juan M. Corchado, Javier Bajo

Affiliation(s):  1BISITE Group, Faculty of Science, University of Salamanca, C/Espejo s/n, Salamanca 37008, Spain; more

Corresponding email(s):   t.c.li@usal.es, t.c.li@mail.nwpu.edu.cn

Key Words:  Particle filter, Resampling, Kullback-Leibler divergence, Kolmogorov-Smirnov statistic


Tian-cheng Li, Gabriel Villarrubia, Shu-dong Sun, Juan M. Corchado, Javier Bajo. Resampling methods for particle filtering: identical distribution, a new method, and comparable study[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(11): 969-984.

@article{title="Resampling methods for particle filtering: identical distribution, a new method, and comparable study",
author="Tian-cheng Li, Gabriel Villarrubia, Shu-dong Sun, Juan M. Corchado, Javier Bajo",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="16",
number="11",
pages="969-984",
year="2015",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1500199"
}

%0 Journal Article
%T Resampling methods for particle filtering: identical distribution, a new method, and comparable study
%A Tian-cheng Li
%A Gabriel Villarrubia
%A Shu-dong Sun
%A Juan M. Corchado
%A Javier Bajo
%J Frontiers of Information Technology & Electronic Engineering
%V 16
%N 11
%P 969-984
%@ 2095-9184
%D 2015
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1500199

TY - JOUR
T1 - Resampling methods for particle filtering: identical distribution, a new method, and comparable study
A1 - Tian-cheng Li
A1 - Gabriel Villarrubia
A1 - Shu-dong Sun
A1 - Juan M. Corchado
A1 - Javier Bajo
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 16
IS - 11
SP - 969
EP - 984
%@ 2095-9184
Y1 - 2015
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1500199


Abstract: 
resampling is a critical procedure that is of both theoretical and practical significance for efficient implementation of the particle filter. To gain an insight of the resampling process and the filter, this paper contributes in three further respects as a sequel to the tutorial (Li et al., 2015). First, identical distribution (ID) is established as a general principle for the resampling design, which requires the distribution of particles before and after resampling to be statistically identical. Three consistent metrics including the (symmetrical) kullback-Leibler divergence, kolmogorov-Smirnov statistic, and the sampling variance are introduced for assessment of the ID attribute of resampling, and a corresponding, qualitative ID analysis of representative resampling methods is given. Second, a novel resampling scheme that obtains the optimal ID attribute in the sense of minimum sampling variance is proposed. Third, more than a dozen typical resampling methods are compared via simulations in terms of sample size variation, sampling variance, computing speed, and estimation accuracy. These form a more comprehensive understanding of the algorithm, providing solid guidelines for either selection of existing resampling methods or new implementations.

This paper provides a further extension to the tutorial Li et al., 2015. First, an identical distribution (ID) principle for re-sampling design is proposed, together with three metrics to evaluate the ID attribute. Next, a new re-sampling method which can achieve the optimal sampling variance is presented. Last, the effectiveness of the proposed method is verified by comparison with conventional re-sampling methods. This paper is well-written and provides great insight into the re-sampling procedure of the particle filter. It will be a good guidance for the researchers working on particle filter.

粒子滤波重采样:同分布原则、一种新方法以及综合对比

目的:重采样方法是粒子滤波设计的重要环节,也是避免或克服“权值退化”和“多样性匮乏”这一对粒子滤波难点问题的关键。当前研究领域已有几十余种重采样方法,然而尚缺乏一个基础性的重采样设计原则以及对这些方法的综合性能对比。针对于此,本文提出重采样“同分布”设计原则,并在此基础上,提出一种能够最大程度满足同分布原则的最优重采样方法。本文希望所提出的重采样同分布原则以及新方法有利于进一步的新方法设计或已有方法的工程选用。
创新点:理论上严格定义了同分布原则作为重采样方法设计的普遍性原则,给出三种同分布测度方法;提出了一种最小采样方差(MSV: minimum sampling variance)最优重采样方法,在满足渐近无偏性的前提下获得最小采样方差。
方法:给出三种“重采样同分布”测度方法:Kullback-Leibler偏差,Kolmogorov-Smirnov统计和采样方差(sampling variance)。所提出的最小采样方差重采样放宽了无偏性条件,仅满足渐近无偏,但获得了最小采样方差(参见定理2-4论证以及仿真性能对比)。
结论:重采样前后粒子的概率分布应该统计上一致(即“同分布”)是重采样方法设计的一个重要原则。明确这一基本原则有利于规范化重采样新方法的设计与工程选用。所提出的MSV重采样新方法渐近无偏,并具有最小采样方差的优异理论特性,即最优地满足同分布原则。算法性能分析表明:大多数无偏或者渐近无偏重采样方法在滤波精度上差异较小,但是在采样方差、计算效率方面差异较大。另一方面,基于一些特殊规则或者问题模型设计的重采样方法可能具有特别优势。

关键词:粒子滤波;重采样;统计同分布;采样方差

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Adiprawita, W., Ahmad, A.S., Sembiring, J., et al., 2011. New resampling algorithm for particle filter localization for mobile robot with 3 ultrasonic sonar sensor. Proc. Int. Conf. on Electrical Engineering and Informatics, p.1-6.

[2]Arulampalam, M.S., Maskell, S., Gordon, N., et al., 2002. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Trans. Signal Process., 50(2):174-188.

[3]Bashi, A.S., Jilkov, V.P., Li, X.R., et al., 2003. Distributed implementations of particle filters. Proc. 6th Int. Conf. on Information Fusion, p.1164-1171.

[4]Beskos, A., Crisan, D., Jasra, A., 2014. On the stability of sequential Monte Carlo methods in high dimensions. Ann. Appl. Probab., 24(4):1396-1445.

[5]Bolić, M., Djurić, P.M., Hong, S., 2003. New resampling algorithms for particle filters. Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, p.589-592.

[6]Cappé, O., Godsill, S.J., Moulines, E., 2007. An overview of existing methods and recent advances in sequential Monte Carlo. Proc. IEEE, 95(5):899-924.

[7]Chen, Y., Xie, J., Liu, J.S., 2005. Stopping-time resampling for sequential Monte Carlo methods. J. R. Stat. Soc. B, 67(2):199-217.

[8]Choe, G.M., Wang, T., Liu, F., et al., 2014. An advanced integrated framework for moving object tracking. J. Zhejiang Univ.-Sci. C (Comput. & Electron.), 15(10):861-877.

[9]Choe, G.M., Wang, T., Liu, F., et al., 2015. Particle filter with spline resampling and global transition model. IET Comput. Vis., 9(2):184-197.

[10]Crisan, D., Doucet, A., 2002. A survey of convergence results on particle filtering methods for practitioners. IEEE Trans. Signal Process., 50(3):736-746.

[11]Crisan, D., Lyons, T., 1999. A particle approximation of the solution of the Kushner-Stratonovitch equation. Probab. Theory Related Fields, 115(4):549-578.

[12]Crisan, D., Del Moral, P., Lyons, T., 1998. Discrete Filtering Using Branching and Interacting Particle Systems. Markov Process. Related Fields, 5(3):293-318.

[13]Das, S.K., Mazumdar, C., 2013. Priori-sensitive resampling particle filter for dynamic state estimation of UUVs. Proc. 8th Int. Workshop on Systems, Signal Processing and Their Applications, p.384-389.

[14]Del Moral, P., Hu, P., Wu, L., 2012. On the concentration properties of interacting particle processes. Found. Trends Mach. Learn., 3(3-4):225-389.

[15]Djurić, P.M., Miguez, J., 2010. Assessment of nonlinear dynamic models by Kolmogorov-Smirnov statistics. IEEE Trans. Signal Process., 58(10):5069-5079.

[16]Djurić, P.M., Kotecha, J.H., Zhang, J., et al., 2003. Particle filtering. IEEE Signal Process. Mag., 20(5):19-38.

[17]Douc, R., Cappé, O., 2005. Comparison of resampling schemes for particle filtering. Proc. 4th Int. Symp. on Image and Signal Processing and Analysis, p.64-69.

[18]Douc, R., Moulines, E., Olsson, J., 2014. Long-term stability of sequential Monte Carlo methods under verifiable conditions. Ann. Appl. Probab., 24(5):1767-1802.

[19]Doucet, A., de Freitas, N., Gordon, N., 2001. Sequential Monte Carlo Methods in Practice. Springer, New York, USA.

[20]Efron, B., Rogosa, D., Tibshirani, R., 2015. Resampling methods of estimation. In: Wright, J.D. (Ed.), International Encyclopedia of the Social & Behavioral Sciences (2nd Ed.). Elsevier, Oxford, p.492-495.

[21]Fearnhead, P., Clifford, P., 2003. On-line inference for hidden Markov models via particle filters. J. R. Stat. Soc. Ser. B, 65(4):887-899.

[22]Fearnhead, P., Liu, Z., 2007. On-line inference for multiple changepoint problems. J. R. Stat. Soc. Ser. B, 69(4):589-605.

[23]Fox, D., 2003. Adapting the sample size in particle filters through KLD-sampling. Int. J. Robot. Res., 22(12):985-1003.

[24]Godsill, S., Vermaak, J., Ng, W., et al., 2007. Models and algorithms for tracking of maneuvering objects using variable rate particle filters. Proc. IEEE, 95(5):925-952.

[25]Gordon, N., Salmond, D., Smith, A.F.M., 1993. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proc. F, 140(2):107-113.

[26]Gustafsson, F., 2010. Particle filter theory and practice with positioning applications. IEEE Aeros. Electron. Syst. Mag., 25(7):53-82.

[27]Hol, J.D., Schon, T.B., Gustafsson, F., 2006. On resampling algorithms for particle filters. Proc. IEEE Nonlinear Statistical Signal Processing Workshop, p.79-82.

[28]Hong, S., Shi, Z., Chen, J., et al., 2010. A low-power memory-efficient resampling architecture for particle filters. Circ. Syst. Signal Process., 29(1):155-167.

[29]Hu, X.L., Schon, T.B., Ljung, L., 2011. A general convergence result for particle filtering. IEEE Trans. Signal Process., 59(7):3424-3429.

[30]Kalman, R.E., 1960. A new approach to linear filtering and prediction problems. J. Basic Eng., 82(1):35-45.

[31]Kitagawa, G., 1996. Monte Carlo filter and smoother and non-Gaussian nonlinear state space models. J. Comput. Graph. Stat., 5(1):1-25.

[32]Kong, A., Liu, J.S., Wong, W.H., 1994. Sequential imputations and Bayesian missing data problems. J. Am. Stat. Assoc., 89(425):278-288.

[33]Kullback, S., Leibler, R.A., 1951. On information and sufficiency. Ann. Math. Stat., 22(1):79-86.

[34]Kwak, N., Kim, G.W., Lee, B.H., 2008. A new compensation technique based on analysis of resampling process in FastSLAM. Robotica, 26(2):205-217.

[35]Lang, H., Li, T., Villarrubia, G., et al., 2015. An adaptive particle filter for indoor robot localization. Proc. 6th Int. Symp. on Ambient Intelligence, p.45-55.

[36]Lenstra, H.W., 1983. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538-548.

[37]Li, T., Sun, S., 2010. Double-resampling based Monte Carlo localization for mobile robot. Acta Autom. Sin., 36(9):1279-1286.

[38]Li, T., Sattar, T.P., Sun, S., 2012. Deterministic resampling: unbiased sampling to avoid sample impoverishment in particle filters. Signal Process., 92(7):1637-1645.

[39]Li, T., Sattar, T.P., Tang, D., 2013a. A fast resampling scheme for particle filters. Proc. Constantinides Int. Workshop on Signal Processing, p.1-4.

[40]Li, T., Sun, S., Sattar, T.P., 2013b. Adapting sample size in particle filters through KLD-resampling. Electron. Lett., 46(2):740-742.

[41]Li, T., Sun, S., Sattar, T.P., et al., 2014. Fight sample degeneracy and impoverishment in particle filters: a review of intelligent approaches. Expert Syst. Appl., 41(8):3944-3954.

[42]Li, T., Bolic, M., Djurić, P.M., 2015. Resampling methods for particle filtering: classification, implementation, and strategies. IEEE Signal Process. Mag., 32(3):70-86.

[43]Li, T., Sun, S., Bolic, M., et al., 2016. Algorithm design for parallel implementation of the SMC-PHD filter. Signal Process., 119:115-127.

[44]Liu, J.S., Chen, R., 1998. Sequential Monte Carlo methods for dynamic systems. J. Am. Stat. Assoc., 93(443):1032-1044.

[45]Liu, J.S., Chen, R., Logvinenko, T., 2001. A theoretical framework for sequential importance sampling and resampling. In: Doucet, A., de Freitas, N., Gordon, N. (Eds.), Sequential Monte Carlo Methods in Practice. Springer, USA, p.225-246.

[46]Mbalawata, I.S., Särkkä, S., 2016. Moment conditions for convergence of particle filters with unbounded importance weights. Signal Process., 118:133-138.

[47]Míguez, J., Bugallo, M.F., Djurić, P.M., 2004. A new class of particle filters for random dynamical systems with unknown statistics. EURASIP J. Adv. Signal Process., 15:2278-2294.

[48]Morelande, M.R., Zhang, A.M., 2011. A mode preserving particle filter. Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, p.3984-3987.

[49]Murray, L., 2012. GPU acceleration of the particle filter: the Metropolis resampler. arXiv:1202.6163v1.

[50]Nielsen, F., 2010. A family of statistical symmetric divergences based on Jensen’s inequality. arXiv:1009.4004.

[51]Pérez, C.J., Martín, J., Rufo, M.J., et al., 2005. Quasi-random sampling importance resampling. Commun. Stat. Simul. Comput., 34(1):97-112.

[52]Robert, C.P., Casella, G., 1999. Monte Carlo Statistical Methods. Springer, New York.

[53]Rubin, D.B., 1987. The calculation of posterior distribution by data augmentation: Comment: a noniterative sampling/ importance resampling alternative to the data augmentation algorithm for creating a few imputations when fractions of missing information are modest: the SIR algorithm. J. Am. Stat. Assoc., 82(398):543-546.

[54]Sileshi, B.G., Ferrer, C., Oliver, J., 2013. Particle filters and resampling techniques: importance in computational complexity analysis. Proc. Conf. on Design and Architectures for Signal and Image Processing, p.319-325.

[55]Simonetto, A., Keviczky, T., 2009. Recent developments in distributed particle filtering: towards fast and accurate algorithms. Proc. 1st IFAC Workshop on Estimation and Control of Networked Systems, p.138-143.

[56]Stano, P.M., Lendek, Z., Babuška, R., 2013. Saturated particle filter: almost sure convergence and improved resampling. Automatica, 49(1):147-159.

[57]Sutharsan, S., Kirubarajan, T., Lang, T., et al., 2012. An optimization-based parallel particle filter for multitarget tracking. IEEE Trans. Aeros. Electron. Syst., 48(2):1601-1618.

[58]Topsoe, F., 2000. Some inequalities for information divergence and related measures of discrimination. IEEE Trans. Inform. Theory, 46(4):1602-1609.

[59]Wang, Y., Djurić, P.M., 2013. Sequential estimation of linear models in distributed settings. Proc. 21st European Signal Processing Conf., p.1-5.

[60]Whiteley, N., 2013. Stability properties of some particle filters. Ann. Appl. Probab., 23(6):2500-2537.

[61]Zhi, R., Li, T., Siyau, M.F., et al., 2014. Applied technology in adapting the number of particles while maintaining the diversity in the particle filter. Adv. Mater. Res., 951:202-207.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE