What the collapse of the ensemble Kalman filter tells us about particle filters

Matthias Morzfeld; Daniel Hodyss; Chris Snyder

doi:10.1080/16000870.2017.1283809

What the collapse of the ensemble Kalman filter tells us about particle filters

Tellus

Volume 69 (2017): Issue 1

By: Matthias Morzfeld, Daniel Hodyss and Chris Snyder

Open Access

|Jan 2017

Abstract

The ensemble Kalman filter (EnKF) is a reliable data assimilation tool for high-dimensional meteorological problems. On the other hand, the EnKF can be interpreted as a particle filter, and particle filters (PF) collapse in high-dimensional problems. We explain that these seemingly contradictory statements offer insights about how PF function in certain high-dimensional problems, and in particular support recent efforts in meteorology to ‘localize’ particle filters, i.e. to restrict the influence of an observation to its neighbourhood.

References

Agapiou , S. , Papaspiliopoulos , O. , Sanz-Alonso , D. and Stuart , A. ( 2016 ). Importance sampling: Computational complexity and intrinsic dimension . submitted, pre-print available on https://arxiv.org .
Search in Google Scholar Back to article
Anderson , J. ( 2001 ). An ensemble adjustment Kalman filter for data assimilation . Mon. Weather Rev. 129 , 2884 – 2903 .
Search in Google Scholar Back to article
Arulampalam , M. , Maskell , S. , Gordon , N. and Clapp , T. ( 2002 ). A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking . IEEE Trans. Signal Process. 50 ( 2 ), 174 – 188 .
Search in Google Scholar Back to article
Bengtsson , T. , Bickel , P. and Li , B. ( 2008 ). Curse of dimensionality revisited: the collapse of importance sampling in very large scale systems., IMS Collections: Probability and Statistics: Essays in Honor of David A . Freedman 2 , 316 – 334 .
Search in Google Scholar Back to article
Bengtsson , T. , Snyder , C. and Nychka , D. ( 2003 ). Toward a nonlinear ensemble filter for high-dimensional systems . J. Geophys. Res. 108 , 8775 .
Search in Google Scholar Back to article
Beskos , A. , Crisan , D. and Jasra , A. ( 2014 ). On the stability of sequential Monte Carlo methods in high dimensions . Ann. Appl. Probab. 24 ( 4 ), 1396 – 1445 .
Search in Google Scholar Back to article
Bickel , P. , Li , B. and Bengtsson , T. ( 2008 ). Sharp failure rates for the bootstrap particle filter in high dimensions., Pushing Limits Contemp. Stat.: Contrib . Honor Jayanta K. Ghosh 3 , 318 – 329 .
Search in Google Scholar Back to article
Bishop , C. , Etherton , B. and Majumdar , S. ( 2001 ). Adaptive sampling with the ensemble transform Kalman filter. part I: Theoretical aspects . Monthly Weather Review 129 , 420 – 436 .
Search in Google Scholar Back to article
Bocquet , M. , Pires , C. and Wu , L. ( 2010 ). Beyond Gaussian statistical modeling in geophysical data assimilation . Mon. Weather Rev. 138 , 2997 – 3023 .
Search in Google Scholar Back to article
Burgers , G. , van Leeuwen , P. J. and Evensen , G. ( 1998 ). Analysis scheme in the ensemble Kalman filter . Mon. Weather Rev. 126 , 1719 – 1724 .
Search in Google Scholar Back to article
Chopin , N. ( 2004 ). Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference . Ann. Statistics 32 ( 6 ), 2385 – 2411 .
Search in Google Scholar Back to article
Chorin , A. and Hald , O. ( 2013 ). Stochastic Tools in Mathematics and Science , 3rd ed. , Springer , New York .
Search in Google Scholar Back to article
Chorin , A. , Lu , F. , Miller , R. , Morzfeld , M. and Tu , X. ( 2016 ). Sampling, feasibility, and priors in Bayesian estimation, Discrete Continuous Dyn . Syst. 36 , 4227 – 4246 .
Search in Google Scholar Back to article
Chorin , A. and Morzfeld , M. ( 2013 ). Conditions for successful data assimilation . J. Geophys. Res. – Atmos. 118 , 11522 – 11533 .
Search in Google Scholar Back to article
Chorin , A. , Morzfeld , M. and Tu , X. ( 2010 ). Implicit particle filters for data assimilation . Commun. Appl. Math. Comput. Sci. 5 ( 2 ), 221 – 240 .
Search in Google Scholar Back to article
Chorin , A. and Tu , X. ( 2009 ). Implicit sampling for particle filters . Proc. Nat. Acad. Sci. 106 ( 41 ), 17249 – 17254 .
Search in Google Scholar Back to article
Doucet , A. ( 1998 ). On sequential Monte Carlo methods for Bayesian filtering . Technical Report . Cambridge : Department of Engineering, University Cambridge .
Search in Google Scholar Back to article
Doucet , A. , de Freitas , N. and Gordon , N. (eds.) ( 2001 ). Sequential Monte Carlo Methods in Practice . Springer , New York .
Search in Google Scholar Back to article
Doucet , A. , Godsill , S. and Andrieu , C. ( 2000 ). On sequential Monte Carlo sampling methods for Bayesian filtering . Stat. Comput. 10 , 197 – 208 .
Search in Google Scholar Back to article
Evensen , G. ( 2006 ). Data Assimilation: The Ensemble Kalman Filter . Springer , New York .
Search in Google Scholar Back to article
Fournier , A. , Hulot , G. , Jault , D. , Kuang , W. , Tangborn , W. , co-authors. ( 2010 ). An introduction to data assimilation and predictability in geomagnetism, Space Sci . Rev. 155 , 247 – 291 .
Search in Google Scholar Back to article
Gaspari , G. and Cohn , S. ( 1999 ). Construction of correlation functions in two and three dimensions . Q. J. R. Meteorol. Soc. 125 , 723 – 757 .
Search in Google Scholar Back to article
Gordon , N. , Salmond , D. and Smith , A. ( 1993 ). Novel approach to nonlinear/non-Gaussian Bayesian state estimation . IEEE Proc. Radar Signal Process. 140 ( 2 ), 107 – 113 .
Search in Google Scholar Back to article
Hamill , T. M. , Whitaker , J. and Snyder , C. ( 2001 ). Distance-dependent filtering of background covariance estimates in an ensemble Kalman filter . Mon. Weather Rev. 129 , 2776 – 2790 .
Search in Google Scholar Back to article
Hodyss , D. ( 2011 ). Ensemble state estimation for nonlinear systems using polynomial expansions in the innovation . Mon. Weather Rev. 139 , 3571 – 3588 .
Search in Google Scholar Back to article
Hodyss , D. and Campbell , W. ( 2013 ). Square root and perturbed observation ensemble generation techniques in Kalman and quadratic ensemble filtering algorithms . Mon. Weather Rev. 141 , 2561 – 2573 .
Search in Google Scholar Back to article
Houtekamer , P. and Mitchell , H. ( 2001 ). A sequential ensemble Kalman filter for atmospheric data assimilation . Mon. Weather Rev. 129 , 123 – 136 .
Search in Google Scholar Back to article
Houtekamer , P. L. , Mitchell , H. L. , Pellerin , G. , Buehner , M. , Charron , M. , co-authors. ( 2005 ). Atmospheric data assimilation with an ensemble Kalman filter: Results with real observations . Mon. Weather Rev. 133 , 604 – 620 .
Search in Google Scholar Back to article
Kalman , R. ( 1960 ). A new approach to linear filtering and prediction theory . Trans. ASME-J. Basic Eng. 82 ( Series D ), 35 – 48 .
Search in Google Scholar Back to article
Kalman , R. and Bucy , R. ( 1961 ). New results in linear filtering and prediction theory . ASME J. Basic Eng. Ser. D 83 , 95 – 108 .
Search in Google Scholar Back to article
Kalos , M. and Whitlock , P. ( 1986 ). Monte Carlo Methods, , 1st ed. , Vol. 1 . John Wiley & Sons , New York .
Search in Google Scholar Back to article
Kantas , N. , Beskos , A. and Jasra , A. ( 2014 ). Sequential Monte Carlo methods for high-dimensional inverse problems: A case study for the Navier-Stokes equations, SIAM/ASA . J. Uncertainty Quantification 2 , 464 – 489 .
Search in Google Scholar Back to article
Kelly , D. , Law , K. and Stuart , A. ( 2014 ). Well-posedness and accuracy of the ensemble Kalman filter in discrete and continuous time . Nonlinearity 27 , 2579 – 2603 .
Search in Google Scholar Back to article
Kelly , D. , Majda , A. and Tong , X. ( 2016a ). Concrete ensemble Kalman filters with rigorous catastrophic filter divergence . Proc. Nat. Acad. Sci. 112 ( 34 ), 10589 – 10594 .
Search in Google Scholar Back to article
Kelly , D. , Majda , A. and Tong , X. ( 2016b ). Nonlinear stability of the ensemble Kalman filter with adaptive covariance inflation . Commun. Math. Sci .
Search in Google Scholar Back to article
Kelly , D. , Majda , A. and Tong , X. ( 2016c ). Nonlinear stability and ergodicity of ensemble based kalman filters . Nonlinearity 29 ( 2 ), 657 – 691 .
Search in Google Scholar Back to article
Khlalil , M. , Sarkar , A. , Adhikari , S. and Poirel , D. ( 2015 ). The estimation of time-invariant parameters of noisy nonlinear oscillatory systems . J. Sound Vib. 344 , 81 – 100 .
Search in Google Scholar Back to article
Klaas , M. , de Freitas , N. and Doucet , A. ( 2005 ). Towards practical N ² Monte Carlo: The marginal particle filter , Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence (UAI-05), Arlington, VA . pp. 308 – 315 .
Search in Google Scholar Back to article
Künsch , H. ( 2005 ). Recursive Monte Carlo filters: Algorithms and theoretical analysis . Ann. Statistics 33 ( 5 ), 1983 – 2021 .
Search in Google Scholar Back to article
Lei , J. and Bickel , P. ( 2011 ). A moment matching ensemble filter for nonlinear non-Gaussian data assimilation . Mon. Weather Rev. 139 , 3964 – 3973 .
Search in Google Scholar Back to article
Liu , J. and Chen , R. ( 1995 ). Blind deconvolution via sequential imputations . J. Am. Stat. Assoc. 90 ( 430 ), 567 – 576 .
Search in Google Scholar Back to article
Majda , A. \ & Tong , X. ( 2016 ). Robustness and accuracy of finite ensemble Kalman filters in large dimensions . arXiv , p. 1606.09321 .
Search in Google Scholar Back to article
Moral , P. D. ( 2004 ). Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications . Springer , New York .
Search in Google Scholar Back to article
Morzfeld , M. and Chorin , A. ( 2012 ). Implicit particle filtering for models with partial noise, and an application to geomagnetic data assimilation, Nonlinear Process . Geophys. 19 , 365 – 382 .
Search in Google Scholar Back to article
Morzfeld , M. , Tu , X. , Atkins , E. and Chorin , A. ( 2012 ). A random map implementation of implicit filters . J. Comput. Phys. 231 , 2049 – 2066 .
Search in Google Scholar Back to article
Owen , A. B. ( 2013 ). Monte Carlo Theory, Methods and Examples . Online at: http://statweb.stanford.edu/~owen/mc/
Search in Google Scholar Back to article
Papadakis , N. , Memin , E. , Cuzol , A. and Gengembre , N. ( 2010 ). Data assimilation with the weighted ensemble Kalman filter . Tellus 62A , 673 – 697 .
Search in Google Scholar Back to article
Penny , S. and Miyoshi , T. ( 2015 ). A local particle filter for high dimensional geophysical systems, Nonlinear Process . Geophys. 2 , 1631 – 1658 .
Search in Google Scholar Back to article
Poterjoy , J. ( 2015 ). A localized particle filter for high-dimensional nonlinear systems . Mon. Weather Rev. 144 , 59 – 76 .
Search in Google Scholar Back to article
Poterjoy , J. and Anderson , J. ( 2016 ). Efficient assimilation of simulated observations in a high-dimensional geophysical system using a localized particle filter . Mon. Weather Rev . 144 , 2007 – 2020 .
Search in Google Scholar Back to article
Raeder , K. , Anderson , J. L. , Collins , N. , Hoar , T. J. , Kay , J. E. and co-authors. ( 2012 ). DART/CAM: An ensemble data assimilation system for CESM atmospheric models . J. Clim. 25 , 6304 – 6317 .
Search in Google Scholar Back to article
Rebeschini , P. and van Handel , R. ( 2015 ). Can local particle filters beat the curse of dimensionality? Ann. Appl. Probab. 25 ( 5 ), 2809 – 2866 .
Search in Google Scholar Back to article
Reich , S. ( 2013 ). A nonparametric ensemble transform method for Bayesian inference . Mon. Weather Rev. 35 ( 4 ), 1337 – 1367 .
Search in Google Scholar Back to article
Snyder , C. ( 2011 ). Particle filters, the "optimal" proposal and high-dimensional systems . Proceedings of the ECMWF Seminar on Data Assimilation for Atmosphere and Ocean , Reading, UK , 1 – 10 .
Search in Google Scholar Back to article
Snyder , C. , Bengtsson , T. , Bickel , P. and Anderson , J. ( 2008 ). Obstacles to high-dimensional particle filtering . Mon. Weather Rev. 136 ( 12 ), 4629 – 4640 .
Search in Google Scholar Back to article
Snyder , C. , Bengtsson , T. and Morzfeld , M. ( 2015 ). Performance bounds for particle filters using the optimal proposal . Mon: Weather Rev. 143 ( 11 ), 4750 – 4761 .
Search in Google Scholar Back to article
Tippet , M. , Anderson , J. , Bishop , C. , Hamill , T. and Whitaker , J. ( 2003 ). Ensemble square root filters . Mon. Weather Rev. 131 , 1485 – 1490 .
Search in Google Scholar Back to article
Tödter , J. and Ahrens , B. ( 2015 ). A second-order exact ensemble square root filter for nonlinear data assimilation . Mon. Weather Rev. 143 , 1337 – 1367 .
Search in Google Scholar Back to article
van Leeuwen , P. ( 2009 ). Particle filtering in geophysical systems . Mon. Weather Rev. 137 , 4089 – 4144 .
Search in Google Scholar Back to article
van Leeuwen , P. , Cheng , Y. and Reich , S. ( 2015 ). Nonlinear Data Assimilation . Springer .
Search in Google Scholar Back to article
Vanden-Eijnden , E. and Weare , J. ( 2012 ). Data assimilation in the low noise regime with application to the Kuroshio . Mon. Weather Rev. 141 , 1822 – 1841 .
Search in Google Scholar Back to article
Wang , X. , Hamill , T. M. , Whitaker , J. S. and Bishop , C. H. ( 2007 ). A comparison of hybrid ensemble transform Kalman filter-optimum interpolation and ensemble square root filter analysis schemes . Mon. Weather Rev. 135 , 1055 – 1076 .
Search in Google Scholar Back to article
Weare , J. ( 2009 ). Particle filtering with path sampling and an application to a bimodal ocean current model . J. Comput. Phys. 228 , 4312 – 4331 .
Search in Google Scholar Back to article
Zaritskii , V. and Shimelevich , L. ( 1975 ). Monte Carlo technique in problems of optimal data processing . Autom Remote Control 12 , 95 – 103 .
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.1080/16000870.2017.1283809 | Journal eISSN: 3035-9554

Journal RSS Feed

Language: English

Page range: 1283809 - 1283809

Submitted on: May 31, 2016

Accepted on: Dec 19, 2016

Published on: Jan 1, 2017

Published by: Stockholm University Press

In partnership with: Paradigm Publishing Services

Keywords:

ensemble Kalman filter,

particle filter,

collapse of particle filters

© 2017 Matthias Morzfeld, Daniel Hodyss, Chris Snyder, published by Stockholm University Press
This work is licensed under the Creative Commons Attribution 4.0 License.

Volume 69 (2017): Issue 1