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

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.

Keywords

Particle filter / Resampling / Kullback-Leibler divergence / Kolmogorov-Smirnov statistic

References

[1] Adiprawita, W., Ahmad, A.S., Sembiring, J., , 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. [doi:10.1109/ICEEI.2011.6021733]

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

[3] Bashi, A.S., Jilkov, V.P., Li, X.R., , 2003. Distributed implementations of particle filters. Proc. 6th Int. Conf. on Information Fusion, p.1164–1171. [doi:10.1109/ICIF. 2003.177369]

[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. [doi:10.1214/13-AAP951]

[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. [doi:10.1109/ICASSP.2003.1202435]

[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. [doi:10.1109/JPROC.2007.893250]

[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. [doi:10.1111/j.1467-9868.2005.00497.x]

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

[9] Choe, G.M., Wang, T., Liu, F., , 2015. Particle filter with spline resampling and global transition model. IET Comput. Vis., 9(2):184–197. [doi:10.1049/iet-cvi.2014.0106]

[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. [doi:10.1109/78.984773]

[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. [doi:10.1007/s004400050249]

[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. [doi:10.1109/WoSSPA.2013.6602396]

[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. [doi:10.1561/2200000026]

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

[16] Djurić, P.M., Kotecha, J.H., Zhang, J., , 2003. Particle filtering. IEEE Signal Process. Mag., 20(5):19–38. [doi:10.1109/MSP.2003.1236770]

[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. [doi:10.1109/ISPA.2005.195385]

[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. [doi:10.1214/13-AAP962]

[19] Doucet, A., de Freitas, N., Gordon, N., 2001. Sequential Monte Carlo Methods in Practice. Springer, New York, USA. [doi:10.1007/978-1-4757-3437-9]

[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. [doi:10.1016/B978-0-08-097086-8.42165-3]

[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. [doi:10.1111/1467-9868.00421]

[22] Fearnhead, P., Liu, Z., 2007. On-line inference for multiple changepoint problems. J. R. Stat. Soc. Ser. B, 69(4): 589–605. [doi:10.1111/j.1467-9868.2007.00601.x]

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

[24] Godsill, S., Vermaak, J., Ng, W., , 2007. Models and algorithms for tracking of maneuvering objects using variable rate particle filters. Proc. IEEE, 95(5):925–952. [doi:10.1109/JPROC.2007.894708]

[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. [doi:10.1049/ip-f-2.1993.0015]

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

[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. [doi:10.1109/NSSPW.2006.4378824]

[28] Hong, S., Shi, Z., Chen, J., , 2010. A low-power memory-efficient resampling architecture for particle filters. Circ. Syst. Signal Process., 29(1):155–167. [doi:10.1007/s00034-009-9117-4]

[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. [doi:10.1109/TSP.2011.2135349]

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

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

[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. [doi:10.1080/01621459.1994.10476469]

[33] Kullback, S., Leibler, R.A., 1951. On information and sufficiency. Ann. Math. Stat., 22(1):79–86. [doi:10.1214/aoms/1177729694]

[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. [doi:10.1017/S0263574707003773]

[35] Lang, H., Li, T., Villarrubia, G., , 2015. An adaptive particle filter for indoor robot localization. Proc. 6th Int. Symp. on Ambient Intelligence, p.45–55. [doi:10.1007/978-3-319-19695-4_5]

[36] Lenstra, H.W., 1983. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538–548. [doi:10.1287/moor.8.4.538]

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

[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. [doi:10.1016/j.sigpro.2011.12.019]

[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. [doi:10.1049/ic.2013.0002]

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

[41] Li, T., Sun, S., Sattar, T.P., , 2014. Fight sample degeneracy and impoverishment in particle filters: a review of intelligent approaches. Expert Syst. Appl., 41(8):3944–3954. [doi:10.1016/j.eswa.2013.12.031]

[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. [doi:10.1109/MSP.2014.2330626]

[43] Li, T., Sun, S., Bolic, M., , 2016. Algorithm design for parallel implementation of the SMC-PHD filter. Signal Process., 119:115–127. [doi:10.1016/j.sigpro.2015.07.013]

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

[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. [doi:10.1007/978-1-4757-3437-9_11]

[46] Mbalawata, I.S., Särkkä, S., 2016. Moment conditions for convergence of particle filters with unbounded importance weights. Signal Process., 118:133–138. [doi:10.1016/j.sigpro.2015.06.018]

[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. [doi:10.1155/S1110865704406039]

[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. [doi:10.1109/ICASSP.2011.5947225]

[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., , 2005. Quasi-random sampling importance resampling. Commun. Stat. Simul. Comput., 34(1):97–112. [doi:10.1081/SAC-200047112]

[52] Robert, C.P., Casella, G., 1999. Monte Carlo Statistical Methods. Springer, New York. [doi:10.1007/978-1-4757-4145-2]

[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. [doi:10.2307/2289460]

[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. [doi:10.3182/20090924-3-IT-4005.00024]

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

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

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

[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. [doi:10.1214/12-AAP909]

[61] Zhi, R., Li, T., Siyau, M.F., , 2014. Applied technology in adapting the number of particles while maintaining the diversity in the particle filter. Adv. Mater. Res., 951:202–207. [doi:10.4028/www.scientific.net/AMR.951.202]