Multi-fidelity generative deep learning turbulent flows
December 2020, 2(4): 351-390. doi: 10.3934/fods.2020017
Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators
Håkon Hoel 1, , Gaukhar Shaimerdenova 2,, and Raúl Tempone 1,2,
Chair of Mathematics for Uncertainty Quantification, RWTH Aachen University, Aachen, Germany
Applied Mathematics and Computational Sciences, KAUST, Thuwal, Saudi Arabia
* Corresponding author: Gaukhar Shaimerdenova
Received September 2020 Published November 2020
Figure(7)
We introduce a new multilevel ensemble Kalman filter method (MLEnKF) which consists of a hierarchy of independent samples of ensemble Kalman filters (EnKF). This new MLEnKF method is fundamentally different from the preexisting method introduced by Hoel, Law and Tempone in 2016, and it is suitable for extensions towards multi-index Monte Carlo based filtering methods. Robust theoretical analysis and supporting numerical examples show that under appropriate regularity assumptions, the MLEnKF method has better complexity than plain vanilla EnKF in the large-ensemble and fine-resolution limits, for weak approximations of quantities of interest. The method is developed for discrete-time filtering problems with finite-dimensional state space and linear observations polluted by additive Gaussian noise.
Keywords: Monte Carlo, multilevel, convergence rates, Kalman filter, ensemble Kalman filter.
Mathematics Subject Classification: 60G35, 65C30, 65Y20.
Citation: Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017
S. I. Aanonsen, G. Nævdal, D. S. Oliver, A. C. Reynolds, B. Vallès, et al., The ensemble Kalman filter in reservoir engineering-a review, Spe Journal, 14 (2009), 393-412. doi: 10.2118/117274-PA. Google Scholar
A. Beskos, A. Jasra, K. J. H. Law, Y. Marzouk and Y. Zhou, Multilevel sequential Monte Carlo with dimension-independent likelihood-informed proposals, SIAM/ASA Journal on Uncertainty Quantification, 6 (2018), 762-786. doi: 10.1137/17M1120993. Google Scholar
A. Beskos, A. Jasra, K. Law, R. Tempone and Y. Zhou, Multilevel sequential monte carlo samplers, Stochastic Processes and their Applications, 127 (2017), 1417-1440. doi: 10.1016/j.spa.2016.08.004. Google Scholar
J. Bezanson, A. Edelman, S. Karpinski and V. B. Shah, Julia: A fresh approach to numerical computing, SIAM Review, 59 (2017), 65–98. doi: 10.1137/141000671. Google Scholar
D. Blömker, C. Schillings, P. Wacker and S. Weissmann, Well Posedness and Convergence Analysis of the Ensemble Kalman Inversion, Inverse Problems, IOP Publishing, (2019). doi: 10.1088/1361-6420/ab149c. Google Scholar
G. Burgers, P. J. van Leeuwen and G. Evensen, Analysis scheme in the ensemble Kalman filter, Monthly Weather Review, 126 (1998), 1719-1724. doi: 10.1175/1520-0493(1998)126<1719:ASITEK>2.0.CO;2. Google Scholar
A. Chernov, H. Hoel, K. J. H. Law, F. Nobile and R. Tempone, Multilevel ensemble Kalman filtering for spatio-temporal processes, preprint, arXiv: 1710.07282. doi: 10.1137/15M100955X. Google Scholar
N. D. Conrad, L. Helfmann, J. Zonker, S. Winkelmann and C. Schütte, Human mobility and innovation spreading in ancient times: A stochastic agent-based simulation approach, in EPJ Data Science, Springer, 7 (2018), 24. Google Scholar
J. de Wiljes, S. Reich and W. Stannat, Long-time stability and accuracy of the ensemble Kalman–Bucy filter for fully observed processes and small measurement noise, SIAM Journal on Applied Dynamical Systems, 17, (2018) 1152–1181. doi: 10.1137/17M1119056. Google Scholar
T. J. Dodwell, C. Ketelsen, R. Scheichl and A. L. Teckentrup, A hierarchical multilevel Markov chain Monte Carlo algorithm with applications to uncertainty quantification in subsurface flow, SIAM/ASA Journal on Uncertainty Quantification, 3 (2015), 1075-1108. doi: 10.1137/130915005. Google Scholar
O. G. Ernst, B. Sprungk and H. Starkloff, Analysis of the ensemble and polynomial chaos Kalman filters in Bayesian inverse problems, SIAM/ASA Journal on Uncertainty Quantification, 3 (2015), 823-851. doi: 10.1137/140981319. Google Scholar
G. Evensen, Sequential data assimilation with a nonlinear quasi-geostrophic model using Monte Carlo methods to forecast error statistics, Journal of Geophysical Research: Oceans, 99(C5) (1998), 10143-10162. doi: 10.1029/94JC00572. Google Scholar
K. Fossum, T. Mannseth and A. S. Stordal, Assessment of multilevel ensemble-based data assimilation for reservoir history matching, Computational Geosciences, 17 (2019), 1-23. doi: 10.1007/s10596-019-09911-x. Google Scholar
M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res., 56 (2008), 607-617. doi: 10.1287/opre.1070.0496. Google Scholar
C. Graham and D. Talay, Stochastic simulation and Monte Carlo methods: Mathematical foundations of stochastic simulation, Springer Science & Business Media, 68 (2013). doi: 10.1007/978-3-642-39363-1. Google Scholar
A. Gregory and C. J. Cotter, A seamless multilevel ensemble transform particle filter, SIAM Journal on Scientific Computing, 39 (2017), A2684–A2701. doi: 10.1137/16M1102021. Google Scholar
A. Gregory, C. J. Cotter and S. Reich, Multilevel ensemble transform particle filtering, SIAM Journal on Scientific Computing, 38 (2016), A1317–A1338. doi: 10.1137/15M1038232. Google Scholar
A. Haji-Ali, F. Nobile and R. Tempone, Multi-index Monte Carlo: When sparsity meets sampling, Numerische Mathematik, 132 (2016), 767-806. doi: 10.1007/s00211-015-0734-5. Google Scholar
A. Haji-Ali and R. Tempone, Multilevel and Multi-index Monte Carlo methods for the McKean–Vlasov equation, Statistics and Computing, 28 (2018), 923-935. doi: 10.1007/s11222-017-9771-5. Google Scholar
S. Heinrich, Multilevel Monte Carlo methods, Large-Scale Scientific Computing, (2001), 58–67. doi: 10.1007/3-540-45346-6_5. Google Scholar
H. Hoel, J. Häppölä and R. Tempone, Construction of a mean square error adaptive Euler–Maruyama method with applications in multilevel Monte Carlo, Monte Carlo and Quasi-Monte Carlo Methods, (2016), 29–86. doi: 10.1007/978-3-319-33507-0_2. Google Scholar
H. Hoel, K. J. H. Law and R. Tempone, Multilevel ensemble Kalman filtering, SIAM Journal on Numerical Analysis, 54 (2016), 1813-1839. doi: 10.1137/15M100955X. Google Scholar
H. Hoel, E. von Schwerin, A. Szepessy and R. Tempone, Adaptive multilevel monte carlo simulation, Numerical Analysis of Multiscale Computations, (2012), 217–234. doi: 10.1007/978-3-642-21943-6_10. Google Scholar
H. Hoel, E. Von Schwerin, A. Szepessy and R. Tempone, Implementation and analysis of an adaptive multilevel Monte Carlo algorithm, Monte Carlo Methods and Applications, 20 (2014), 1-41. doi: 10.1515/mcma-2013-0014. Google Scholar
P. L. Houtekamer and H. L. Mitchell, Data assimilation using an ensemble Kalman filter technique, Monthly Weather Review, 126 (1998), 796-811. doi: 10.1175/1520-0493(1998)126<0796:DAUAEK>2.0.CO;2. Google Scholar
P. L. Houtekamer, H. L. Mitchell, G. Pellerin, M. Buehner, M. Charron, L. Spacek and B. Hansen, Atmospheric data assimilation with an ensemble Kalman filter: Results with real observations, Monthly Weather Review, 133 (2005), 604-620. doi: 10.1175/MWR-2864.1. Google Scholar
A. Jasra, K. Kamatani, K. J. H. Law and Y. Zhou, Multilevel particle filters, SIAM Journal on Numerical Analysis, 55 (2017), 3068-3096. doi: 10.1137/17M1111553. Google Scholar
R. E. Kalman, A new approach to linear filtering and prediction problems, Journal of basic Engineering, 82 (1960), 35-45. doi: 10.1115/1.3662552. Google Scholar
E. Kalnay, Atmospheric Modeling, Data Assimilation and Predictability, Cambridge university press, (2003). doi: 10.1017/CBO9780511802270. Google Scholar
D. T. B. Kelly, K. J. H. Law and A. M. Stuart, Well-posedness and accuracy of the ensemble Kalman filter in discrete and continuous time, Nonlinearity, 27 (2014), 2579. doi: 10.1088/0951-7715/27/10/2579. Google Scholar
P. E. Kloeden and E. Platen, Numerical solution of stochastic differential equations, in Applications of Mathematics (New York), 82, Springer-Verlag, Berlin, 1992. doi: 10.1007/978-3-662-12616-5. Google Scholar
E. Kwiatkowski and J. Mandel, Convergence of the square root ensemble Kalman filter in the large ensemble limit, SIAM/ASA Journal on Uncertainty Quantification, 3 (2015), 1-17. doi: 10.1137/140965363. Google Scholar
J. Latz, I. Papaioannou and E. Ullmann, Multilevel sequential Monte Carlo for Bayesian inverse problems, Journal of Computational Physics, 368 (2018), 154-178. doi: 10.1016/j.jcp.2018.04.014. Google Scholar
F. Le Gland, V. Monbet, V. Tran, et al., Large sample asymptotics for the ensemble Kalman filter, in Oxford University Press (eds. D. Crisan, B. Rozovskii), 2011,598–631. Google Scholar
J. Mandel, L. Cobb and J. D. Beezley, On the convergence of the ensemble Kalman filter, Applications of Mathematics, 56 (2011), 533-541. doi: 10.1007/s10492-011-0031-2. Google Scholar
P. D. Moral, A. Jasra, K. J. H. Law and Y. Zhou, Multilevel sequential Monte Carlo samplers for normalizing constants, ACM Transactions on Modeling and Computer Simulation (TOMACS), 27 (2017), 20. doi: 10.1145/3092841. Google Scholar
B. Peherstorfer, K. Willcox and M. Gunzburger, Optimal model management for multifidelity Monte Carlo estimation, SIAM Journal on Scientific Computing, 38 (2016), A3163–A3194. doi: 10.1137/15M1046472. Google Scholar
A. Popov, C. Mou, T. Iliescu and A. Sandu, A multifidelity ensemble Kalman filter with reduced order control variates, preprint, arXiv: 2007.00793. Google Scholar
B. V. Rosić, A. Kučerová, J. Sỳkora, O. Pajonk, A. Litvinenko and H. G. Matthies, Parameter identification in a probabilistic setting, Engineering Structures, 50 (2013), 179-196. Google Scholar
C. Schillings and A. M. Stuart, Convergence analysis of ensemble Kalman inversion: The linear, noisy case, Applicable Analysis, 97 (2018), 107-123. doi: 10.1080/00036811.2017.1386784. Google Scholar
C. Schütte and M. Sarich, Metastability and Markov State Models in Molecular Dynamics, American Mathematical Soc., 24 (2013). doi: 10.1090/cln/024. Google Scholar
A. Szepessy, R. Tempone and G. E. Zouraris, Adaptive weak approximation of stochastic differential equations, Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 54 (2001), 1169-1214. doi: 10.1002/cpa.10000. Google Scholar
X. T. Tong, A. J. Majda and D. Kelly, Nonlinear stability and ergodicity of ensemble based Kalman filters, Nonlinearity, 29 (2016), 657. doi: 10.1088/0951-7715/29/2/657. Google Scholar
Figure 1. Illustration, based on the nonlinear dynamics (5), of the contracting property which can produce almost identical prediction densities (middle panels) for the Bayes filter and MFEnKF even when the preceding updated densities differ notably
Figure 2. One prediction-update iteration of the MLEnKF estimator described in Section 2.4.1. Green and pink ovals represent fine- and coarse-level prediction-state particles, respectively, sharing the same initial condition and driving noise $ \omega^{\ell} $ and the respective squares represent fine- and coarse-level updated-state particles sharing the perturbed observartions. The MLEnKF estimator is obtained by iid copies of pairwise-coupled samples, cf (9)
Figure 3. Top row: comparison of the runtime versus RMSE for the QoIs mean (left) and variance (right) over $ \mathcal{N} = 10 $ observation times for the problem in Section 3.1. The solid-crossed line represents MLEnKF, the solid-asterisk line represents the original MLEnKF and the bottom reference triangle with the slope $ \frac{1}{2} $, the solid-bulleted line represents EnKF and the upper reference triangle with the slope $ \frac{1}{3} $. Bottom row: similar plots over $ \mathcal{N} = 20 $ observation times
Figure 4. Realization of the double-well SDE from Section 3.2 over time $ \mathcal{N} = 20 $ observation times (solid line) and observations (dots)
Figure 5. Left column: Well transition of the EnKF ensemble when the measurements are located in the opposite well. Right column: Animation of the particle paths of the corresponding EnKF ensemble during the well-transition, and the resulting kernel density estimations of the EnKF prediction and update densities (Section 3.2). For practical purposes, EnKF with only 7 particles is not very robust. We use so few particles in this computation for the sole purpose of obtaining a visually clear illustration of the ensemble transition
Figure 7. (a) The inequality $ \min(\beta s,1)<s $ (green line). (b) The equality $ \min(\beta s,1) = s $ (blue line). (c) The inequality $ \min(\beta s,1)>s $ (red line). The dash lines correspond to the function $ y(s) = \min(\beta s, 1) $ and the dotted lines refer to the function $ y(s) = \beta s $ varying by different cases of $ \beta $ value
Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020 doi: 10.3934/fods.2020018
Philipp Harms. Strong convergence rates for markovian representations of fractional processes. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020367
Xiuli Xu, Xueke Pu. Optimal convergence rates of the magnetohydrodynamic model for quantum plasmas with potential force. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 987-1010. doi: 10.3934/dcdsb.2020150
George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
Yukio Kan-On. On the limiting system in the Shigesada, Kawasaki and Teramoto model with large cross-diffusion rates. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3561-3570. doi: 10.3934/dcds.2020161
Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020465
Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
Toshiko Ogiwara, Danielle Hilhorst, Hiroshi Matano. Convergence and structure theorems for order-preserving dynamical systems with mass conservation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3883-3907. doi: 10.3934/dcds.2020129
Takiko Sasaki. Convergence of a blow-up curve for a semilinear wave equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1133-1143. doi: 10.3934/dcdss.2020388
Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226
Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345
Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304
Gheorghe Craciun, Jiaxin Jin, Casian Pantea, Adrian Tudorascu. Convergence to the complex balanced equilibrium for some chemical reaction-diffusion systems with boundary equilibria. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1305-1335. doi: 10.3934/dcdsb.2020164
Jan Březina, Eduard Feireisl, Antonín Novotný. On convergence to equilibria of flows of compressible viscous fluids under in/out–flux boundary conditions. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021009
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
Håkon Hoel Gaukhar Shaimerdenova Raúl Tempone