Ergodicity and Accuracy of Optimal Particle Filters for Bayesian Data Assimilation

Abstract

Data assimilation refers to the methodology of combining dynamical models and observed data with the objective of improving state estimation. Most data assimilation algorithms are viewed as approximations of the Bayesian posterior (filtering distribution) on the signal given the observations. Some of these approximations are controlled, such as particle filters which may be refined to produce the true filtering distribution in the large particle number limit, and some are uncontrolled, such as ensemble Kalman filter methods which do not recover the true filtering distribution in the large ensemble limit. Other data assimilation algorithms, such as cycled 3DVAR methods, may be thought of as controlled estimators of the state, in the small observational noise scenario, but are also uncontrolled in general in relation to the true filtering distribution. For particle filters and ensemble Kalman filters it is of practical importance to understand how and why data assimilation methods can be effective when used with a fixed small number of particles, since for many large-scale applications it is not practical to deploy algorithms close to the large particle limit asymptotic. In this paper, the authors address this question for particle filters and, in particular, study their accuracy (in the small noise limit) and ergodicity (for noisy signal and observation) without appealing to the large particle number limit. The authors first overview the accuracy and minorization properties for the true filtering distribution, working in the setting of conditional Gaussianity for the dynamics-observation model. They then show that these properties are inherited by optimal particle filters for any fixed number of particles, and use the minorization to establish ergodicity of the filters. For completeness we also prove large particle number consistency results for the optimal particle filters, by writing the update equations for the underlying distributions as recursions. In addition to looking at the optimal particle filter with standard resampling, they derive all the above results for (what they term) the Gaussianized optimal particle filter and show that the theoretical properties are favorable for this method, when compared to the standard optimal particle filter.

Keywords

Particle filters / Data assimilation / Ergodic theory

References

[1] Akashi H, Kumamoto H. Random sampling approach to state estimation in switching environments. Automatica, 1977, 13(4): 429-434

[2] Atar R, Zeitouni O. Exponential stability for nonlinear filtering. Annales de l’IHP Probabilitiés et statistiques, 1997, 33: 697-725

[3] Bauer P, Thorpe A, Brunet G. The quiet revolution of numerical weather prediction. Nature, 2015, 525(7567): 47-55

[4] Blömker D, Law K, Stuart A M, Zygalakis K C. Accuracy and stability of the continuous-time 3DVAR filter for the Navier-Stokes equation. Nonlinearity, 2013, 26(8): 2193

[5] Budhiraja A, Ocone D. Exponential stability of discrete-time filters for bounded observation noise. Systems & Control Letters, 1997, 30(4): 185-193

[6] Burgers G, Leeuwen P J V, Evensen G. Analysis scheme in the ensemble Kalman filter. Monthly Weather Review, 1998, 126(6): 1719-1724

[7] Chorin A J, Tu X M. Implicit sampling for particle filters. Proceedings of the National Academy of Sciences, 2009, 106(41): 17249-17254

[8] Crisan D, Heine K. Stability of the discrete time filter in terms of the tails of noise distributions. Journal of the London Mathematical Society, 2008, 78(2): 441-458

[9] Moral P D, Kurtzmann A, Tugaut J. On the stability and the uniform propagation of chaos of extended ensemble Kalman-Bucy filters, 2016

[10] Douc R, Fort G, Moulines E, Priouret P. Forgetting the initial distribution for hidden Markov models. Stochastic Processes and Their Applications, 2009, 119(4): 1235-1256

[11] Douc R, Moulines E, Olsson J. Optimality of the auxiliary particle filter. Probability and Mathematical Statistics, 2009, 29(1): 1-28

[12] Doucet A, Freitas N D, Gordon N. An introduction to sequential Monte Carlo methods, Sequential Monte Carlo Methods in Practice, 2010, New York: Springer-Verlag

[13] Doucet A, Godsill S, Andrieu C. On sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing, 2000, 10(3): 197-208

[14] Evensen G. Using the extended Kalman filter with a multilayer quasi-geostrophic ocean model. Journal of Geophysical Research: Oceans, 1992, 97(C11): 17905-17924

[15] Evensen G. The ensemble Kalman filter: Theoretical formulation and practical implementation. Ocean Dynamics, 2003, 53(4): 343-367

[16] Ghil M, Malanotte-Rizzoli P. Data assimilation in meteorology and oceanography. Advances in Geophysics, 1991, 33: 141-266

[17] Handel R V. The stability of conditional Markov processes and Markov chains in random environments. The Annals of Probability, 2009, 37(5): 1876-1925

[18] Harlim J, Majda A J. Catastrophic filter divergence in filtering nonlinear dissipative systems. Communications in Mathematical Sciences, 2010, 8(1): 27-43

[19] Houtekamer P L, Mitchell H L. Ensemble Kalman filtering. Quarterly Journal of the Royal Meteorological Society, 2005, 131(613): 3269-3289

[20] Johansen A M, Doucet A. A note on auxiliary particle filters. Statistics, 2008, 78(12): 1498-1504

[21] Kelly D, Majda A J, Tong X T. Concrete ensemble Kalman filters with rigorous catas-trophic filter divergence. Proceedings of the National Academy of Sciences, 2015, 112(34): 10589-10594

[22] Kelly D, Vanden-Eijnden E, Weare J. Personal Communications, 2016

[23] Kelly D T B, Law K J H, Stuart A M. Well-posedness and accuracy of the ensemble Kalman filter in discrete and continuous time. Nonlinearity, 2014, 27(10): 2579

[24] Kleptsyna M L, Veretennikov A Y. On discrete time ergodic filters with wrong initial data. Probability Theory and Related Fields, 2008, 141(3-4): 411-444

[25] Kunita H. Asymptotic behavior of the nonlinear filtering errors of Markov processes. Journal of Multivariate Analysis, 1971, 1(4): 365-393

[26] Law K, Stuart A, Zygalakis K. Data Assimilation, 2015, New York: Springer-Verlag

[27] Law K J H, Sanz-Alonso D, Shukla A, Stuart A M. Filter accuracy for the Lorenz 96 model: fixed versus adaptive observation operators. Physica D: Nonlinear Phenomena, 2016, 325: 1-13

[28] Law K J H, Shukla A, Stuart A M. Analysis of the 3DVAR filter for the partially observed Lorenz ’63 model. Discrete and Continuous Dynamical Systems A, 2014, 34: 1061-1078

[29] Law K J H, Tembine H, Tempone R. Deterministic mean-field ensemble Kalman filtering, 2014

[30] Leeuwen P J V. Particle filtering in geophysical systems. Monthly Weather Review, 2009, 137(12): 4089-4114

[31] Leeuwen P J V. Nonlinear data assimilation in geosciences: An extremely efficient particle filter. Quarterly Journal of the Royal Meteorological Society, 2010, 136(653): 1991-1999

[32] Liu J S, Chen R. Blind deconvolution via sequential imputations. Journal of the American Statistical Association, 1995, 90(430): 567-576

[33] Lorenc A C. Analysis methods for numerical weather prediction. Quarterly Journal of the Royal Meteorological Society, 1986, 112(474): 1177-1194

[34] Majda A J, Harlim J. Filtering Complex Turbulent Systems, 2012, Cambridge: Cambridge University Press

[35] Majda A J, Tong X T. Robustness and accuracy of finite ensemble Kalman filters in large dimensions, 2016

[36] Moodey A J F, Lawless A S, Potthast R W E, Leeuwen P J V. Nonlinear error dynamics for cycled data assimilation methods. Inverse Problems, 2013, 29(2): 025002

[37] Pitt M K, Shephard N. Filtering via simulation: Auxiliary particle filters. Journal of the American Statistical Association, 1999, 94(446): 590-599

[38] Poyiadjis G, Doucet A, Singh S S. Particle approximations of the score and observed information matrix in state space models with application to parameter estimation. Biometrika, 2011, 98(1): 65-80

[39] Rebeschini P, Handel R V. Can local particle filters beat the curse of dimensionality?. The Annals of Applied Probability, 2015, 25(5): 2809-2866

[40] Sanz-Alonso D, Stuart A M. Long-time asymptotics of the filtering distribution for partially observed chaotic dynamical systems. SIAM/ASA Journal on Uncertainty Quantification, 2015, 3(1): 1200-1220

[41] Sedigh-Sarvestani M, Albers D J, Gluckman B J. Data assimilation of glucose dynamics for use in the intensive care unit, 2012 5437-5440

[42] Sedigh-Sarvestani M, Schiff S J, Gluckman B J. Reconstructing mammalian sleep dynamics with data assimilation. PLoS Comput Biol, 2012, 8(11): e1002788

[43] Snyder C. Particle filters, the “optimal” proposal and high-dimensional systems, 2011

[44] Snyder C, Bengtsson T, Morzfeld M. Performance bounds for particle filters using the optimal proposal. Monthly Weather Review, 2015, 143(11): 4750-4761

[45] Tadic V Z B, Doucet A. Asymptotic properties of recursive maximum likelihood estimation in non-linear state-space models, 2018

[46] Thrun S. Particle filters in robotics, Proceedings of the Eighteenth Conference on Uncertainty in artificial Intelligence, 2002, CA: Morgan Kaufmann Publishers Inc., San Francisco 511-518

[47] Tong X T, Handel R V. Ergodicity and stability of the conditional distributions of nondegenerate Markov chains. Annals of Applied Probability, 2012, 22(4): 1495-1540

[48] Tong X T, Majda A J, Kelly D. Nonlinear stability of the ensemble Kalman filter with adaptive covariance inflation. Communications in Mathematical Sciences, 2016, 14(5): 1283-1313

[49] Tong X T, Majda A J, Kelly D. Nonlinear stability and ergodicity of ensemble based Kalman filters. Nonlinearity, 2016, 29(2): 657

[50] Work D B, Blandin S, Tossavainen O P. A traffic model for velocity data assimilation. Applied Mathematics Research Express, 2010, 2010(1): 1-35

[51] Zaritskii V S, Svetnik V B, Šimelevišc L I. Monte-Carlo technique in problems of optimal information processing. Avtomatika i Telemekhanika, 1975, 36(12): 95-103