Article Contents
Article Contents

# Error analysis for numerical formulation of particle filter

• 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.
Mathematics Subject Classification: Primary: 65C35; Secondary: 65C05.

 Citation:

•  [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.