Error analysis for numerical formulation of particle filter

Previous Article
Euler-Maclaurin expansions and approximations of hypersingular integrals
DCDS-B Home
This Issue
Next Article
Stability and convergence of time-stepping methods for a nonlocal model for diffusion

July 2015, 20(5): 1337-1354. doi: 10.3934/dcdsb.2015.20.1337

Error analysis for numerical formulation of particle filter

Xiaoying Han ^1, , Jinglai Li ^2, and Dongbin Xiu ^3,

1.	221 Parker Hall, Department of Mathematics and Statistics, Auburn University, Auburn, AL 36849
2.	Institute of Natural sciences, Department of Mathematics, MOE Key Lab of Scientic and Engineering Computing, Shanghai JiaoTong University, 800 Dongchuan Rd, Minhang 200240, Shanghai, China
3.	Department of Mathematics, Scientific Computing and Imagining Institute, The University of Utah, Salt Lake City, UT 84112, United States

Received December 2013 Revised January 2015 Published May 2015

Abstract
Related Papers

As an approximation of the optimal stochastic filter, particle filter is a widely used tool for numerical prediction of complex systems when observation data are available. In this paper, we conduct an error analysis from a numerical analysis perspective. That is, we investigate the numerical error, which is defined as the difference between the numerical implementation of particle filter and its continuous counterpart, and demonstrate that the error consists of discretization errors for solving the dynamic equations numerically and sampling errors for generating the random particles. We then establish convergence of the numerical particle filter to the continuous optimal filter and provide bounds for the convergence rate. Remarkably, our analysis suggests that more frequent data assimilation may lead to larger numerical errors of the particle filter. Numerical examples are provided to verify the theoretical findings.

Keywords: data assimilation, sequential Monte Carlo., particle filter, Bayesian filer.

Mathematics Subject Classification: Primary: 65C35; Secondary: 65C0.

Citation: Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337

References:

[1]	S. Arulampalam, S. Maskell, N. Gordon and T. Clapp, A tutorial on particle filters for on-line non-linear/non-Gaussian Bayesian tracking, IEEE Tran. Signal Process., 50 (2002), 174-188.
[2]	O. Cappé, S. J. Godsill and E. Moulines, An Overview of Existing Methods and Recent Advances in Sequential Monte Carlo, Proc. IEEE 95, May 2007.
[3]	S. Chib, F. Nardari and N. Shephard, Markov chain Monte Carlo methods for stochastic volatility models, J. Econometr., 108 (2002), 281-316. doi: 10.1016/S0304-4076(01)00137-3.
[4]	S. E. Cohn, An introduction to estimation theory, J. Meteor. Soc. Jpn., 75 (1997), 257-288.
[5]	D. Crisan and A. Doucet, A survey of convergence results on particle filtering for practitioners, IEEE Trans. Signal Process., 50 (2002), 736-746. doi: 10.1109/78.984773.
[6]	A. Doucet, N. Defreitas and N. Gordon, Sequential Monte Carlo Methods in Practice, Springer, 2001. doi: 10.1007/978-1-4757-3437-9.
[7]	A Doucet, S Godsill and C Andrieu, On sequential Monte Carlo sampling methods for Bayesian filtering, Stat. & Comput., 10 (2000), 197-208.
[8]	Y. Ho and R. Lee, A Bayesian approach to problems in stochastic estimation and control, IEEE Tran. Auto. Control, 9 (1964), 333-339.
[9]	X. Hu, T. B. Schön and L. Ljung, A basic convergence result for particle filtering, IEEE Tran. Signal Process., 56 (2008), 1337-1348. doi: 10.1109/TSP.2007.911295.
[10]	A. H. Jazwinski, Stochastic Processes and Filtering Theory, Academic Press, 1970.
[11]	L. Kuznetsov, K. Ide and C. K. R. T. Jones, A method for assimilation of Lagrangian data, Mon. Wea. Rev., 131 (2003), 2247-2260. doi: 10.1175/1520-0493(2003)131<2247:AMFAOL>2.0.CO;2.
[12]	C. Lemieux, D. Ormoneit and D. J. Fleet, Lattice Particle Filters, Proc. 17th Ann. Conf. UAI, 2002.
[13]	J. Li and D. Xiu, On numerical properties of the ensemble kalman filter for data assimilation, Comput. Methods Appl. Mech. Engrg., 197 (2008), 3574-3583. doi: 10.1016/j.cma.2008.03.022.
[14]	J. Liu and R. Chen, Sequential Monte Carlo methods for dynamic systems, J. Am. Stat. Assoc., 93 (1998), 1032-1044. doi: 10.1080/01621459.1998.10473765.
[15]	A. Quarteroni, R. Sacco and F. Saleri, Numerical Mathematics, Springer-Verlag, New York, 2000.
[16]	H. Salman, L. Kuznetsov, C. K. R. T. Jones and K. Ide, A method for assimilating Lagrangian data into a shallow-water equation ocean model, Mon. Wea. Rev., 134 (2006), 1081-1101. doi: 10.1175/MWR3104.1.
[17]	E. T. Spiller, A. Budhirajab, K. Ide and C. K. R. T. Jones, Modified particle filter methods for assimilating Lagrangian data into a point-vortex model, Phys. D, 237 (2008), 1498-1506. doi: 10.1016/j.physd.2008.03.023.
[18]	S. Thrun, Particle Filters in Robotics, Proc. 17th Ann. Conf. UAI, 2002.
[19]	P. Van Leeuwen, Particle filtering in geophysical systems, Mon. Wea. Rev., 137 (2009), 4089-4114.
[20]	G. Welch and G. Bishop, An introduction to the Kalman filter, Tech. Rep. TR95-041.

show all references

References:

[1]	S. Arulampalam, S. Maskell, N. Gordon and T. Clapp, A tutorial on particle filters for on-line non-linear/non-Gaussian Bayesian tracking, IEEE Tran. Signal Process., 50 (2002), 174-188.
[2]	O. Cappé, S. J. Godsill and E. Moulines, An Overview of Existing Methods and Recent Advances in Sequential Monte Carlo, Proc. IEEE 95, May 2007.
[3]	S. Chib, F. Nardari and N. Shephard, Markov chain Monte Carlo methods for stochastic volatility models, J. Econometr., 108 (2002), 281-316. doi: 10.1016/S0304-4076(01)00137-3.
[4]	S. E. Cohn, An introduction to estimation theory, J. Meteor. Soc. Jpn., 75 (1997), 257-288.
[5]	D. Crisan and A. Doucet, A survey of convergence results on particle filtering for practitioners, IEEE Trans. Signal Process., 50 (2002), 736-746. doi: 10.1109/78.984773.
[6]	A. Doucet, N. Defreitas and N. Gordon, Sequential Monte Carlo Methods in Practice, Springer, 2001. doi: 10.1007/978-1-4757-3437-9.
[7]	A Doucet, S Godsill and C Andrieu, On sequential Monte Carlo sampling methods for Bayesian filtering, Stat. & Comput., 10 (2000), 197-208.
[8]	Y. Ho and R. Lee, A Bayesian approach to problems in stochastic estimation and control, IEEE Tran. Auto. Control, 9 (1964), 333-339.
[9]	X. Hu, T. B. Schön and L. Ljung, A basic convergence result for particle filtering, IEEE Tran. Signal Process., 56 (2008), 1337-1348. doi: 10.1109/TSP.2007.911295.
[10]	A. H. Jazwinski, Stochastic Processes and Filtering Theory, Academic Press, 1970.
[11]	L. Kuznetsov, K. Ide and C. K. R. T. Jones, A method for assimilation of Lagrangian data, Mon. Wea. Rev., 131 (2003), 2247-2260. doi: 10.1175/1520-0493(2003)131<2247:AMFAOL>2.0.CO;2.
[12]	C. Lemieux, D. Ormoneit and D. J. Fleet, Lattice Particle Filters, Proc. 17th Ann. Conf. UAI, 2002.
[13]	J. Li and D. Xiu, On numerical properties of the ensemble kalman filter for data assimilation, Comput. Methods Appl. Mech. Engrg., 197 (2008), 3574-3583. doi: 10.1016/j.cma.2008.03.022.
[14]	J. Liu and R. Chen, Sequential Monte Carlo methods for dynamic systems, J. Am. Stat. Assoc., 93 (1998), 1032-1044. doi: 10.1080/01621459.1998.10473765.
[15]	A. Quarteroni, R. Sacco and F. Saleri, Numerical Mathematics, Springer-Verlag, New York, 2000.
[16]	H. Salman, L. Kuznetsov, C. K. R. T. Jones and K. Ide, A method for assimilating Lagrangian data into a shallow-water equation ocean model, Mon. Wea. Rev., 134 (2006), 1081-1101. doi: 10.1175/MWR3104.1.
[17]	E. T. Spiller, A. Budhirajab, K. Ide and C. K. R. T. Jones, Modified particle filter methods for assimilating Lagrangian data into a point-vortex model, Phys. D, 237 (2008), 1498-1506. doi: 10.1016/j.physd.2008.03.023.
[18]	S. Thrun, Particle Filters in Robotics, Proc. 17th Ann. Conf. UAI, 2002.
[19]	P. Van Leeuwen, Particle filtering in geophysical systems, Mon. Wea. Rev., 137 (2009), 4089-4114.
[20]	G. Welch and G. Bishop, An introduction to the Kalman filter, Tech. Rep. TR95-041.

[1]	Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems and Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81
[2]	Juntao Yang, Viet Ha Hoang. Multilevel Markov Chain Monte Carlo for Bayesian inverse problem for Navier-Stokes equation. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022033
[3]	Jiangqi Wu, Linjie Wen, Jinglai Li. Resampled ensemble Kalman inversion for Bayesian parameter estimation with sequential data. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 837-850. doi: 10.3934/dcdss.2021045
[4]	Olli-Pekka Tossavainen, Daniel B. Work. Markov Chain Monte Carlo based inverse modeling of traffic flows using GPS data. Networks and Heterogeneous Media, 2013, 8 (3) : 803-824. doi: 10.3934/nhm.2013.8.803
[5]	Zhiyan Ding, Qin Li. Constrained Ensemble Langevin Monte Carlo. Foundations of Data Science, 2022, 4 (1) : 37-70. doi: 10.3934/fods.2021034
[6]	Marc Bocquet, Julien Brajard, Alberto Carrassi, Laurent Bertino. Bayesian inference of chaotic dynamics by merging data assimilation, machine learning and expectation-maximization. Foundations of Data Science, 2020, 2 (1) : 55-80. doi: 10.3934/fods.2020004
[7]	Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic and Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291
[8]	Ajay Jasra, Kody J. H. Law, Yaxian Xu. Markov chain simulation for multilevel Monte Carlo. Foundations of Data Science, 2021, 3 (1) : 27-47. doi: 10.3934/fods.2021004
[9]	Theodore Papamarkou, Alexey Lindo, Eric B. Ford. Geometric adaptive Monte Carlo in random environment. Foundations of Data Science, 2021, 3 (2) : 201-224. doi: 10.3934/fods.2021014
[10]	Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335
[11]	Jiakou Wang, Margaret J. Slattery, Meghan Henty Hoskins, Shile Liang, Cheng Dong, Qiang Du. Monte carlo simulation of heterotypic cell aggregation in nonlinear shear flow. Mathematical Biosciences & Engineering, 2006, 3 (4) : 683-696. doi: 10.3934/mbe.2006.3.683
[12]	Jin-Won Kim, Amirhossein Taghvaei, Yongxin Chen, Prashant G. Mehta. Feedback particle filter for collective inference. Foundations of Data Science, 2021, 3 (3) : 543-561. doi: 10.3934/fods.2021018
[13]	Alexandre J. Chorin, Fei Lu, Robert N. Miller, Matthias Morzfeld, Xuemin Tu. Sampling, feasibility, and priors in data assimilation. Discrete and Continuous Dynamical Systems, 2016, 36 (8) : 4227-4246. doi: 10.3934/dcds.2016.36.4227
[14]	Chjan C. Lim, Joseph Nebus, Syed M. Assad. Monte-Carlo and polyhedron-based simulations I: extremal states of the logarithmic N-body problem on a sphere. Discrete and Continuous Dynamical Systems - B, 2003, 3 (3) : 313-342. doi: 10.3934/dcdsb.2003.3.313
[15]	Joseph Nebus. The Dirichlet quotient of point vortex interactions on the surface of the sphere examined by Monte Carlo experiments. Discrete and Continuous Dynamical Systems - B, 2005, 5 (1) : 125-136. doi: 10.3934/dcdsb.2005.5.125
[16]	Mazyar Zahedi-Seresht, Gholam-Reza Jahanshahloo, Josef Jablonsky, Sedighe Asghariniya. A new Monte Carlo based procedure for complete ranking efficient units in DEA models. Numerical Algebra, Control and Optimization, 2017, 7 (4) : 403-416. doi: 10.3934/naco.2017025
[17]	Débora A. F. Albanez, Maicon J. Benvenutti. Continuous data assimilation algorithm for simplified Bardina model. Evolution Equations and Control Theory, 2018, 7 (1) : 33-52. doi: 10.3934/eect.2018002
[18]	Jochen Bröcker. Existence and uniqueness for variational data assimilation in continuous time. Mathematical Control and Related Fields, 2021 doi: 10.3934/mcrf.2021050
[19]	Jules Guillot, Emmanuel Frénod, Pierre Ailliot. Physics informed model error for data assimilation. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022059
[20]	Andrea Arnold, Daniela Calvetti, Erkki Somersalo. Vectorized and parallel particle filter SMC parameter estimation for stiff ODEs. Conference Publications, 2015, 2015 (special) : 75-84. doi: 10.3934/proc.2015.0075

2021 Impact Factor: 1.497

Tools

Metrics

Other articles
by authors

on AIMS
Xiaoying Han Jinglai Li Dongbin Xiu
on Google Scholar
Xiaoying Han Jinglai Li Dongbin Xiu

[Back to Top]