×

Particles resampling scheme using regularized optimal transport for sequential Monte Carlo filters. (English) Zbl 1402.93247

Summary: A resampling method is presented for improving the performance of particle filters by using adaptive numbers of the resampling particles. The proposed method replaces the resampling step of a sequential importance resampling particle filter with regularized optimal transport that makes use of the transport plan to warp a posteriori weights into desired weights. The basis of the method is the same as an ensemble transform particle filter that uses the linear transformation step in the resampling of particles. However, the linear transformation step in ensemble transform particle filter is computationally expensive and needs relaxation matching between the two samples for robust processing. Furthermore, its performance can be degraded if the number of the effective particles becomes below the required number of particles, which represents the needed particle number of importance sampling. Therefore, in this paper, a regularized optimal transport method is used to deal with computational load reduction and relaxation matching in the resampling step by using a modified Sinkhorn-Knopp algorithm that considers the process iteration rate convergence. In order to maintain the proper number of the effective particles for states estimation, Kullback-Leibler distance sampling method is also implemented in the resampling process. The proposed method is evaluated by theoretical analysis including simple simulations compared with the conventional resampling methods. According to the simulations, the proposed method indicates that estimation accuracy is better than conventional methods with small number of the effective particles.

MSC:

93E11 Filtering in stochastic control theory
93E10 Estimation and detection in stochastic control theory
93E20 Optimal stochastic control
90C15 Stochastic programming
49Q20 Variational problems in a geometric measure-theoretic setting
93-04 Software, source code, etc. for problems pertaining to systems and control theory
Full Text: DOI

References:

[1] SärkkäS. Bayesian Filtering and Smoothing. Vol. 3. New York, NY: Cambridge University Press; 2013. · Zbl 1274.62021
[2] MbalawataIS, SärkkäS. Moment conditions for convergence of particle filters with unbounded importance weights. Signal Process. 2016;118:133‐138.
[3] LiT, BolicM, DjuricPM. Resampling methods for particle filtering: classification, implementation, and strategies. IEEE Signal Process Mag. 2015;32(3):70‐86.
[4] LuJ, TokinagaS. Estimation of structural changes in nonlinear time series models by using particle filters and genetic programming. Int J Adapt Control Signal Process. 2016;30(1):60‐75. · Zbl 1348.93257
[5] TangX, HuangJ, ZhouJ, WeiP. A sigma point‐based resampling algorithm in particle filter. Int J Adapt Control Signal Process. 2012;26(11):1013‐1023. · Zbl 1276.93077
[6] RisticB, ArulampalamS, GordonNJ. Beyond the Kalman Filter: Particle Filters for Tracking Applications; Boston, MA: Artech House; 2004. · Zbl 1092.93041
[7] FearnheadP. Sequential Monte Carlo Methods in Filter Theory [Doctoral dissertation]. Oxford, UK: University of Oxford; 1998.
[8] GordonNJ, SalmondDJ, SmithAFM. Novel approach to nonlinear/non‐Gaussian Bayesian state estimation. IEE Proc F Radar Signal Process. 1993;140(2):107‐113.
[9] DoucetA, De FreitasN, GordonN. An introduction to sequential Monte Carlo methods. Sequential Monte Carlo Methods in Practice. New York, NY: Springer; 2001:3‐14. · Zbl 1056.93576
[10] GilksWR, BerzuiniC. Following a moving target—Monte Carlo inference for dynamic Bayesian models. J R Stat Soc Series B Stat Methodol. 2001;63(1):127‐146. · Zbl 0976.62021
[11] ParkS, HwangJP, KimE, KangH‐J. A new evolutionary particle filter for the prevention of sample impoverishment. IEEE Trans Evol Comput. 2009;13(4):801‐809.
[12] OrgunerU, GustafssonF. Risk‐sensitive particle filters for mitigating sample impoverishment. IEEE Trans Signal Process. 2008;56(10):5001‐5012. · Zbl 1390.94347
[13] LiT, SattarTP, SunS. Deterministic resampling: unbiased sampling to avoid sample impoverishment in particle filters. Signal Process. 2012;92(7):1637‐1645.
[14] ReichS. A nonparametric ensemble transform method for Bayesian inference. SIAM J Sci Comput. 2013;35(4):A2013‐A2024. · Zbl 1362.65007
[15] ChustagulpromN, ReichS, ReinhardtM. A hybrid ensemble transform particle filter for nonlinear and spatially extended dynamical systems. SIAM/ASA J Uncertain Quantification. 2016;4(1):592‐608. · Zbl 1343.65009
[16] GregoryA, CotterCJ. A seamless multilevel ensemble transform particle filter. SIAM J Sci Comput. 2017;39(6):A2684‐A2701. · Zbl 1378.65022
[17] CuturiM. Sinkhorn distances: lightspeed computation of optimal transport. Advances in Neural Information Processing Systems. San Diego, CA: NIPS Foundation; 2013;2292‐2300.
[18] FoxD. Adapting the sample size in particle filters through KLD‐sampling. Int J Robotics Res. 2003;22(12):985‐1003.
[19] LiT, SunS, SattarTP. Adapting sample size in particle filters through KLD‐resampling. Electron Lett. 2013;49(12):740‐742.
[20] KnightPA. The Sinkhorn-Knopp algorithm: convergence and applications. SIAM J Matrix Anal Appl. 2008;30(1):261‐275. · Zbl 1166.15301
[21] JohnsonNL, KotzS, BalakrishnanN. Continuous Univariate Distributions. Vol. 1. Hoboken, NJ: John Wiley &Sons, Ltd; 1994. · Zbl 0811.62001
[22] ChakrabortyS, ChattarajS, MukherjeeA. Performance evaluation of particle filter resampling techniques for improved estimation of misalignment and trajectory deviation. Multidimens Syst Signal Process. 2018;29(3):821‐838. · Zbl 1448.94054
[23] HolJD, SchonTB, GustafssonF. On resampling algorithms for particle filters. Paper presented at: 2006 IEEE Nonlinear Statistical Signal Processing Workshop; 2006; Cambridge, UK.
[24] RobertC, CasellaG. Monte Carlo statistical methods. Springer Science & Business Media; 2013.
[25] CochranWG. Sampling Techniques. Hoboken, NJ: John Wiley & Sons, Ltd; 2007.
[26] PeleO, WermanM. Fast and robust earth mover’s distances. Paper presented at: 2009 IEEE 12th International Conference on Computer Vision; 2009; Kyoto, Japan.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.