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

Error analysis for numerical formulation of particle filter

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.
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. 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, (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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1080/01621459.1998.10473765. Google Scholar

[15]

A. Quarteroni, R. Sacco and F. Saleri, Numerical Mathematics,, Springer-Verlag, (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. 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. 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. 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. 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, (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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1080/01621459.1998.10473765. Google Scholar

[15]

A. Quarteroni, R. Sacco and F. Saleri, Numerical Mathematics,, Springer-Verlag, (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. 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. 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. 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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

Issam S. Strub, Julie Percelay, Olli-Pekka Tossavainen, Alexandre M. Bayen. Comparison of two data assimilation algorithms for shallow water flows. Networks & Heterogeneous Media, 2009, 4 (2) : 409-430. doi: 10.3934/nhm.2009.4.409

[12]

Yuan Pei. Continuous data assimilation for the 3D primitive equations of the ocean. Communications on Pure & Applied Analysis, 2019, 18 (2) : 643-661. doi: 10.3934/cpaa.2019032

[13]

Juan Carlos De los Reyes, Estefanía Loayza-Romero. Total generalized variation regularization in data assimilation for Burgers' equation. Inverse Problems & Imaging, 2019, 13 (4) : 755-786. doi: 10.3934/ipi.2019035

[14]

Joshua Hudson, Michael Jolly. Numerical efficacy study of data assimilation for the 2D magnetohydrodynamic equations. Journal of Computational Dynamics, 2019, 6 (1) : 131-145. doi: 10.3934/jcd.2019006

[15]

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

[16]

Qifeng Cheng, Xue Han, Tingting Zhao, V S Sarma Yadavalli. Improved particle swarm optimization and neighborhood field optimization by introducing the re-sampling step of particle filter. Journal of Industrial & Management Optimization, 2019, 15 (1) : 177-198. doi: 10.3934/jimo.2018038

[17]

Laura Martín-Fernández, Gianni Gilioli, Ettore Lanzarone, Joaquín Míguez, Sara Pasquali, Fabrizio Ruggeri, Diego P. Ruiz. A Rao-Blackwellized particle filter for joint parameter estimation and biomass tracking in a stochastic predator-prey system. Mathematical Biosciences & Engineering, 2014, 11 (3) : 573-597. doi: 10.3934/mbe.2014.11.573

[18]

Daniela Calvetti, Erkki Somersalo. Microlocal sequential regularization in imaging. Inverse Problems & Imaging, 2007, 1 (1) : 1-11. doi: 10.3934/ipi.2007.1.1

[19]

Benjamin Jourdain, Julien Reygner. Optimal convergence rate of the multitype sticky particle approximation of one-dimensional diagonal hyperbolic systems with monotonic initial data. Discrete & Continuous Dynamical Systems - A, 2016, 36 (9) : 4963-4996. doi: 10.3934/dcds.2016015

[20]

Ye Chen, Keith W. Hipel, D. Marc Kilgour. A multiple criteria sequential sorting procedure. Journal of Industrial & Management Optimization, 2008, 4 (3) : 407-423. doi: 10.3934/jimo.2008.4.407

2018 Impact Factor: 1.008

Metrics

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

Other articles
by authors

[Back to Top]