American Institute of Mathematical Sciences

Advanced
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 Scienti c 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

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 & 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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[4]

S. E. Cohn, An introduction to estimation theory, J. Meteor. Soc. Jpn., 75 (1997), 257-288. Google Scholar

[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.  Google Scholar

[6]

A. Doucet, N. Defreitas and N. Gordon, Sequential Monte Carlo Methods in Practice, Springer, 2001. doi: 10.1007/978-1-4757-3437-9.  Google Scholar

[7]

A Doucet, S Godsill and C Andrieu, On sequential Monte Carlo sampling methods for Bayesian filtering, Stat. & Comput., 10 (2000), 197-208. Google Scholar

[8]

Y. Ho and R. Lee, A Bayesian approach to problems in stochastic estimation and control, IEEE Tran. Auto. Control, 9 (1964), 333-339.  Google Scholar

[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.  Google Scholar

[10]

A. H. Jazwinski, Stochastic Processes and Filtering Theory, Academic Press, 1970. Google Scholar

[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.  Google Scholar

[12]

C. Lemieux, D. Ormoneit and D. J. Fleet, Lattice Particle Filters, Proc. 17th Ann. Conf. UAI, 2002. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

A. Quarteroni, R. Sacco and F. Saleri, Numerical Mathematics, Springer-Verlag, New York, 2000.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

S. Thrun, Particle Filters in Robotics, Proc. 17th Ann. Conf. UAI, 2002. Google Scholar

[19]

P. Van Leeuwen, Particle filtering in geophysical systems, Mon. Wea. Rev., 137 (2009), 4089-4114. Google Scholar

[20]

G. Welch and G. Bishop, An introduction to the Kalman filter,, Tech. Rep. TR95-041., (): 95.   Google Scholar

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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[4]

S. E. Cohn, An introduction to estimation theory, J. Meteor. Soc. Jpn., 75 (1997), 257-288. Google Scholar

[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.  Google Scholar

[6]

A. Doucet, N. Defreitas and N. Gordon, Sequential Monte Carlo Methods in Practice, Springer, 2001. doi: 10.1007/978-1-4757-3437-9.  Google Scholar

[7]

A Doucet, S Godsill and C Andrieu, On sequential Monte Carlo sampling methods for Bayesian filtering, Stat. & Comput., 10 (2000), 197-208. Google Scholar

[8]

Y. Ho and R. Lee, A Bayesian approach to problems in stochastic estimation and control, IEEE Tran. Auto. Control, 9 (1964), 333-339.  Google Scholar

[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.  Google Scholar

[10]

A. H. Jazwinski, Stochastic Processes and Filtering Theory, Academic Press, 1970. Google Scholar

[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.  Google Scholar

[12]

C. Lemieux, D. Ormoneit and D. J. Fleet, Lattice Particle Filters, Proc. 17th Ann. Conf. UAI, 2002. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

A. Quarteroni, R. Sacco and F. Saleri, Numerical Mathematics, Springer-Verlag, New York, 2000.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

S. Thrun, Particle Filters in Robotics, Proc. 17th Ann. Conf. UAI, 2002. Google Scholar

[19]

P. Van Leeuwen, Particle filtering in geophysical systems, Mon. Wea. Rev., 137 (2009), 4089-4114. Google Scholar

[20]

G. Welch and G. Bishop, An introduction to the Kalman filter,, Tech. Rep. TR95-041., (): 95.   Google Scholar

[1]

Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems & Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81
[2]

Jiangqi Wu, Linjie Wen, Jinglai Li. Resampled ensemble Kalman inversion for Bayesian parameter estimation with sequential data. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021045
[3]

Olli-Pekka Tossavainen, Daniel B. Work. Markov Chain Monte Carlo based inverse modeling of traffic flows using GPS data. Networks & Heterogeneous Media, 2013, 8 (3) : 803-824. doi: 10.3934/nhm.2013.8.803
[4]

Zhiyan Ding, Qin Li. Constrained Ensemble Langevin Monte Carlo. Foundations of Data Science, 2021  doi: 10.3934/fods.2021034
[5]

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
[6]

Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic & Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291
[7]

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
[8]

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
[9]

Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335
[10]

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
[11]

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
[12]

Alexandre J. Chorin, Fei Lu, Robert N. Miller, Matthias Morzfeld, Xuemin Tu. Sampling, feasibility, and priors in data assimilation. Discrete & Continuous Dynamical Systems, 2016, 36 (8) : 4227-4246. doi: 10.3934/dcds.2016.36.4227
[13]

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 & Continuous Dynamical Systems - B, 2003, 3 (3) : 313-342. doi: 10.3934/dcdsb.2003.3.313
[14]

Joseph Nebus. The Dirichlet quotient of point vortex interactions on the surface of the sphere examined by Monte Carlo experiments. Discrete & Continuous Dynamical Systems - B, 2005, 5 (1) : 125-136. doi: 10.3934/dcdsb.2005.5.125
[15]

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 & Optimization, 2017, 7 (4) : 403-416. doi: 10.3934/naco.2017025
[16]

Débora A. F. Albanez, Maicon J. Benvenutti. Continuous data assimilation algorithm for simplified Bardina model. Evolution Equations & Control Theory, 2018, 7 (1) : 33-52. doi: 10.3934/eect.2018002
[17]

Jochen Bröcker. Existence and uniqueness for variational data assimilation in continuous time. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021050
[18]

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
[19]

Xin Li, Feng Bao, Kyle Gallivan. A drift homotopy implicit particle filter method for nonlinear filtering problems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021097
[20]

Sahani Pathiraja, Wilhelm Stannat. Analysis of the feedback particle filter with diffusion map based approximation of the gain. Foundations of Data Science, 2021, 3 (3) : 615-645. doi: 10.3934/fods.2021023

2020 Impact Factor: 1.327

Tools

Metrics

  • PDF downloads (82)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy