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]

Geir Evensen, Javier Amezcua, Marc Bocquet, Alberto Carrassi, Alban Farchi, Alison Fowler, Pieter L. Houtekamer, Christopher K. Jones, Rafael J. de Moraes, Manuel Pulido, Christian Sampson, Femke C. Vossepoel. An international initiative of predicting the SARS-CoV-2 pandemic using ensemble data assimilation. Foundations of Data Science, 2020  doi: 10.3934/fods.2021001

[2]

Eduard Feireisl, Elisabetta Rocca, Giulio Schimperna, Arghir Zarnescu. Weak sequential stability for a nonlinear model of nematic electrolytes. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 219-241. doi: 10.3934/dcdss.2020366

[3]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269

[4]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026

[5]

Anna Anop, Robert Denk, Aleksandr Murach. Elliptic problems with rough boundary data in generalized Sobolev spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020286

[6]

Haruki Umakoshi. A semilinear heat equation with initial data in negative Sobolev spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 745-767. doi: 10.3934/dcdss.2020365

[7]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[8]

Van Duong Dinh. Random data theory for the cubic fourth-order nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020284

[9]

Bao Wang, Alex Lin, Penghang Yin, Wei Zhu, Andrea L. Bertozzi, Stanley J. Osher. Adversarial defense via the data-dependent activation, total variation minimization, and adversarial training. Inverse Problems & Imaging, 2021, 15 (1) : 129-145. doi: 10.3934/ipi.2020046

[10]

Weihong Guo, Yifei Lou, Jing Qin, Ming Yan. IPI special issue on "mathematical/statistical approaches in data science" in the Inverse Problem and Imaging. Inverse Problems & Imaging, 2021, 15 (1) : I-I. doi: 10.3934/ipi.2021007

[11]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076

[12]

Karol Mikula, Jozef Urbán, Michal Kollár, Martin Ambroz, Ivan Jarolímek, Jozef Šibík, Mária Šibíková. An automated segmentation of NATURA 2000 habitats from Sentinel-2 optical data. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1017-1032. doi: 10.3934/dcdss.2020348

[13]

Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077

2019 Impact Factor: 1.27

Metrics

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

Other articles
by authors

[Back to Top]