Error analysis for numerical formulation of particle filter

Xiaoying Han; Jinglai Li; Dongbin Xiu

doi:10.3934/dcdsb.2015.20.1337

Article Contents

2015, Volume 20, Issue 5: 1337-1354. Doi: 10.3934/dcdsb.2015.20.1337

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

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 Scientic and Engineering Computing, Shanghai JiaoTong University, 800 Dongchuan Rd, Minhang 200240, Shanghai
3.
Department of Mathematics, Scientific Computing and Imagining Institute, The University of Utah, Salt Lake City, UT 84112

Received: December 2013

Revised: January 2015

Published: July 2015

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.