A drift homotopy implicit particle filter method for nonlinear filtering problems

Xin Li; Feng Bao; Kyle Gallivan

doi:10.3934/dcdss.2021097

Article Contents

2022, Volume 15, Issue 4: 727-746. Doi: 10.3934/dcdss.2021097

This issue Previous Article Stochastic quasi-subgradient method for stochastic quasi-convex feasibility problems Next Article ISALT: Inference-based schemes adaptive to large time-stepping for locally Lipschitz ergodic systems

A drift homotopy implicit particle filter method for nonlinear filtering problems

Department of Mathematics, Florida State University, Tallahassee, Florida

^* Corresponding author
^* Corresponding author

Received: January 31, 2021

Revised: May 31, 2021

Early access: August 2021

Published: April 2022

Abstract Full Text(HTML) Figure(8) / Table(4) Related Papers Cited by

Abstract

In this paper, we develop a drift homotopy implicit particle filter method. The methodology of our approach is to adopt the concept of drift homotopy in the resampling procedure of the particle filter method for solving the nonlinear filtering problem, and we introduce an implicit particle filter method to improve the efficiency of the drift homotopy resampling procedure. Numerical experiments are carried out to demonstrate the effectiveness and efficiency of our drift homotopy implicit particle filter.

Keywords:

Mathematics Subject Classification: 60G35, 62M20, 93E11.

Citation:

Full Text(HTML)

Figure 1. Double well potential case 1: $ \alpha = 1 $, $ \sigma = 1.5 $, $ R = 1.5 $

Download: Full-size image PowerPoint slide

Figure 2. Double well potential case 2: $ \alpha = 1 $, $ \sigma = 1 $, $ R = 1 $ with state switch

Download: Full-size image PowerPoint slide

Figure 3. Double well potential case 3: $ \alpha = 10 $, $ \sigma = 1 $, $ R = 2 $ with state switch

Download: Full-size image PowerPoint slide

Figure 4. Tracking performance for $ 4000 $ steps

Download: Full-size image PowerPoint slide

Figure 5. Tracking errors for $ 4000 $ steps

Download: Full-size image PowerPoint slide

Figure 6. Tracking performance with rapid change in the state

Download: Full-size image PowerPoint slide

Figure 7. Tracking errors with rapid change in the state

Download: Full-size image PowerPoint slide

Figure 8. Mean square errors with respect to observation gaps

Download: Full-size image PowerPoint slide

Table 1.

Algorithm: Drift homotopy implicit particle filter (DHIPF)
Initialize the particle cloud $ \{x_0^{(i)}\}_{i=1}^{N_p} $, the number of drift homotopy levels $ L $ with the intermediate drift function $ b $ and the constant sequence $ \{\beta_l\}_{l=0}^{L} $, and the reference random variable $ \xi $ for the implicit particle filter procedure.
while $ n =0, 1, 2, \cdots $, do
for: particles $ i = 1, 2, \cdots, N_p $,
for: drift homotopy levels $ l = 0, 1, 2, \cdots, L-1 $,
-: Construct the drift homotopy dynamics (10); -: Solve for $ \psi_{l}^{n+1, i} $ in the equation (17) with the initial guess $ \hat{x}_{n+1, l}^{(i)} $; -: Generate the sample $ \hat{x}_{n+1, l+1}^{(i)} $ through $ \exp\big(- \frac{\xi^{T} \xi}{2}\big) J_{\psi_l^{n+1, i}}^{-1} $;
end for
end for
The particles $ \{x_{n+1}^{(i)}\}_{i = 1}^{N_p} : = \{\hat{x}_{n+1, L}^{(i)}\}_{i = 1}^{N_p} $ provide an empirical distribution for the filtering density $ p(X_{n+1} \| Y_{1:n+1}) $
end while

| Show Table

DownLoad: CSV

Table 2. Example 1. Performance comparison for Case 1

	APF	EnKF	IPF	DHPF	DHIPF
CPU Time	$ 9.703 $	$ 0.365625 $	$ 0.0938 $	$ 48.563 $	$ \bf{0.312} $
MSE	$ 2.03 E-3 $	$ 5.22 E-3 $	$ 1.10 E-3 $	$ 5.92 E-4 $	$ \bf{4.60 E-4} $

| Show Table

DownLoad: CSV

Table 3. Example 1. Performance comparison for Case 2

	APF	EnKF	IPF	DHPF	DHIPF
CPU Time	$ 9.391 $	$ 0.578 $	$ 0.109 $	$ 43.344 $	$ \bf{0.297} $
MSE	$ 6.29 E-1 $	$ 1.36 $	$ 5.28 E-3 $	$ 1.78 E-3 $	$ \bf{1.08 E-3} $

| Show Table

DownLoad: CSV

Table 4. Example 1. Performance comparison for Case 3

	APF	EnKF	IPF	DHPF	DHIPF
CPU Time	$ 9.563 $	$ 0.453 $	$ 0.156 $	$ 50.188 $	$ \bf{0.422} $
MSE	$ 1.80 $	$ 1.99 $	$ 5.02 E-3 $	$ 1.35 E-2 $	$ \bf{1.59 E-3} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C. Andrieu, A. Doucet and R. Holenstein, Particle markov chain monte carlo methods, J. R. Statist. Soc. B, 72 (2010), 269-342. doi: 10.1111/j.1467-9868.2009.00736.x.
[2]	C. Andrieu and G. O. Roberts, The pseudo-marginal approach for efficient monte carlo computations, Ann. Statist., 37 (2009), 697-725. doi: 10.1214/07-AOS574.
[3]	R. Archibald, F. Bao and X. Tu, A direct filter method for parameter estimation, J. Comput. Phys., 398 (2019), 108871, 17 pp. doi: 10.1016/j.jcp.2019.108871.
[4]	F. Bao, R. Archibald and P. Maksymovych, Lévy backward SDE filter for jump diffusion processes and its applications in material sciences, Communications in Computational Physics, 27 (2020), 589-618. doi: 10.4208/cicp.OA-2018-0238.
[5]	F. Bao, Y. Cao and H. Chi, Adjoint forward backward stochastic differential equations driven by jump diffusion processes and its application to nonlinear filtering problems, Int. J. Uncertain. Quantif., 9 (2019), 143-159. doi: 10.1615/Int.J.UncertaintyQuantification.2019028300.
[6]	F. Bao, Y. Cao and X. Han, An implicit algorithm of solving nonlinear filtering problems, Communications in Computational Physics, 16 (2014), 382-402. doi: 10.4208/cicp.180313.130214a.
[7]	F. Bao, Y. Cao and X. Han, Forward backward doubly stochastic differential equations and optimal filtering of diffusion processes, Communications in Mathematical Sciences, 18 (2020), 635-661. doi: 10.4310/CMS.2020.v18.n3.a3.
[8]	F. Bao, Y. Cao, A. Meir and W. Zhao, A first order scheme for backward doubly stochastic differential equations, SIAM/ASA J. Uncertain. Quantif., 4 (2016), 413-445. doi: 10.1137/14095546X.
[9]	F. Bao, Y. Cao, C. Webster and G. Zhang, A hybrid sparse-grid approach for nonlinear filtering problems based on adaptive-domain of the Zakai equation approximations, SIAM/ASA J. Uncertain. Quantif., 2 (2014), 784-804. doi: 10.1137/140952910.
[10]	F. Bao, Y. Cao and W. Zhao, Numerical solutions for forward backward doubly stochastic differential equations and zakai equations, International Journal for Uncertainty Quantification, 1 (2011), 351-367. doi: 10.1615/Int.J.UncertaintyQuantification.2011003508.
[11]	F. Bao, Y. Cao and W. Zhao, A first order semi-discrete algorithm for backward doubly stochastic differential equations, Discrete and Continuous Dynamical Systems-Series B, 20 (2015), 1297-1313. doi: 10.3934/dcdsb.2015.20.1297.
[12]	F. Bao, Y. Cao and W. Zhao, A backward doubly stochastic differential equation approach for nonlinear filtering problems, Commun. Comput. Phys., 23 (2018), 1573-1601. doi: 10.4208/cicp.oa-2017-0084.
[13]	F. Bao and V. Maroulas, Adaptive meshfree backward SDE filter, SIAM J. Sci. Comput., 39 (2017), A2664–A2683. doi: 10.1137/16M1100277.
[14]	A. J. Chorin and X. Tu, Implicit sampling for particle filters, Proc. Nat. Acad. Sc. USA, 106 (2009), 17249-17254. doi: 10.1073/pnas.0909196106.
[15]	D. Crisan, Exact rates of convergence for a branching particle approximation to the solution of the Zakai equation, Ann. Probab., 31 (2003), 693-718. doi: 10.1214/aop/1048516533.
[16]	D. Crisan and A. Doucet, A survey of convergence results on particle filtering methods for practitioners, IEEE Trans. Sig. Proc., 50 (2002), 736-746. doi: 10.1109/78.984773.
[17]	A. Doucet and A. M. Johansen, A tutorial on particle filtering and smoothing: Fifteen years later, The Oxford Handbook of Nonlinear Filtering, 2011,656–704.
[18]	O. Dyck, M. Ziatdinov, S. Jesse, F. Bao, A. Yousefzadi Nobakht, A. Maksov, B. G. Sumpter, R. Archibald, K. J. H. Law and S. V. Kalinin, Probing potential energy landscapes via electron-beam-induced single atom dynamics, Acta Materialia, 203 (2021), 116508.
[19]	G. Evensen, Data Assimilation: The Ensemble Kalman Filter, Springer, 2009. doi: 10.1007/978-3-642-03711-5.
[20]	G. Evensen, The ensemble Kalman filter for combined state and parameter estimation: Monte Carlo techniques for data assimilation in large systems, IEEE Control Syst. Mag., 29 (2009), 83-104. doi: 10.1109/MCS.2009.932223.
[21]	E. Gobet, G. Pagès, H. Pham and J. Printems, Discretization and simulation of the Zakai equation, SIAM J. Numer. Anal., 44 (2006), 2505–2538 (electronic). doi: 10.1137/050623140.
[22]	N. J Gordon, D. J Salmond and A. F. M. Smith, Novel approach to nonlinear/non-gaussian bayesian state estimation, IEE Proceeding-F, 140 (1993), 107-113. doi: 10.1049/ip-f-2.1993.0015.
[23]	S. J. Julier and J. K. Uhlmann, Unscented filtering and nonlinear estimation, Proceedings of the IEEE, 92 (2004), 401-422. doi: 10.1109/JPROC.2003.823141.
[24]	K. Kang, V. Maroulas, I. Schizas and F. Bao, Improved distributed particle filters for tracking in a wireless sensor network, Comput. Statist. Data Anal., 117 (2018), 90-108. doi: 10.1016/j.csda.2017.07.009.
[25]	H. R. Kunsch, Particle filters, Bernoulli, 19 (2013), 1391-1403. doi: 10.3150/12-BEJSP07.
[26]	F. Le Gland, Time discretization of nonlinear filtering equations, In Proceedings of the 28th IEEE Conference on Decision and Control, Vol. 1–3* (Tampa, FL, 1989)*, 2601–2606, New York, 1989. IEEE.
[27]	V. Maroulas and P. Stinis, Improved particle filters for multi-target tracking, Journal of Computational Physics, 231 (2012), 602-611. doi: 10.1016/j.jcp.2011.09.023.
[28]	M. Morzfeld, X. Tu, E. Atkins and A. J. Chorin, A random map implementation of implicit filters, J. Comput. Phys., 231 (2012), 2049-2066. doi: 10.1016/j.jcp.2011.11.022.
[29]	M. K. Pitt and N. Shephard, Filtering via simulation: Auxiliary particle filters, J. Amer. Statist. Assoc., 94 (1999), 590-599. doi: 10.1080/01621459.1999.10474153.
[30]	C. Snyder, T. Bengtsson, P. Bickel and J. Anderson, Obstacles to high-dimensional particle filtering, Mon. Wea. Rev., 136 (2008), 4629-4640. doi: 10.1175/2008MWR2529.1.
[31]	T. Song and J. Speyer, A stochastic analysis of a modified gain extended kalman filter with applications to estimation with bearings only measurements, IEEE Transactions on Automatic Control, 30 (1985), 940-949.
[32]	X. T. Tong, A. J. Majda and D. Kelly, Nonlinear stability and ergodicity of ensemble based Kalman filters, Nonlinearity, 29 (2016), 657-691. doi: 10.1088/0951-7715/29/2/657.
[33]	P. J. van Leeuwen, Nonlinear data assimilation in geosciences: An extremely efficient particle filter, Q. J. Roy. Meteor. Soc., 136 (2010), 1991-1999. doi: 10.1002/qj.699.
[34]	B. Wang, X. Zou and J. Zhu, Data assimilation and its applications, Proceedings of the National Academy of Sciences, 97 (2000), 11143-11144. doi: 10.1073/pnas.97.21.11143.
[35]	M. Zakai, On the optimal filtering of diffusion processes, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 11 (1969), 230-243. doi: 10.1007/BF00536382.