Article Contents
Article Contents

# Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds

• * Corresponding author: Zhiyan Ding

Zhiyan Ding and Qin Li are supported in part by NSF CAREER DMS-1750488, NSF TRIPODS 1740707 and Wisconsin Data Science Initiative. The work of Jianfeng Lu is supported in part by National Science Foundation via grants DMS-1454939 and DMS-2012286. All three authors thank the two anonymous referees for the very helpful suggestions

• Ensemble Kalman Inversion (EnKI) [23] and Ensemble Square Root Filter (EnSRF) [36] are popular sampling methods for obtaining a target posterior distribution. They can be seem as one step (the analysis step) in the data assimilation method Ensemble Kalman Filter [17,3]. Despite their popularity, they are, however, not unbiased when the forward map is nonlinear [12,16,25]. Important Sampling (IS), on the other hand, obtains the unbiased sampling at the expense of large variance of weights, leading to slow convergence of high moments.

We propose WEnKI and WEnSRF, the weighted versions of EnKI and EnSRF in this paper. It follows the same gradient flow as that of EnKI/EnSRF with weight corrections. Compared to the classical methods, the new methods are unbiased, and compared with IS, the method has bounded weight variance. Both properties will be proved rigorously in this paper. We further discuss the stability of the underlying Fokker-Planck equation. This partially explains why EnKI, despite being inconsistent, performs well occasionally in nonlinear settings. Numerical evidence will be demonstrated at the end.

Mathematics Subject Classification: Primary: 62D05; Secondary: 82C31.

 Citation:

• Figure 1.  Example $1$: from left top to bottom right: WEnKI; WEnSRF; WEnKF, as shown in Remark 1 and equation (44); IS; EnKI and EnSRF. (All evolutional equation take $\Delta t = 10^{-3}$.)

Figure 2.  Example $2$: from left top to bottom right: WEnKI; WEnSRF; WEnKF; IS; EnKI and EnSRF

Figure 3.  Example $3$: from left top to bottom right: WEnKI; WEnSRF; WEnKF; IS; EnKI and EnSRF

Figure 4.  Example 3: $\log( {\rm{Var}}(Nw(t))+1)$ for WEnKI, WEnSRF and IS

Figure 5.  Example $4$: from left top to bottom right: WEnKI; WEnSRF; WEnKF; IS; EnKI and EnSRF

Figure 6.  Example $5$: from left top to bottom right: WEnKI; WEnSRF; WEnKF; IS; EnKI and EnSRF

Figure 7.  Example 5: $\log( {\rm{Var}}(Nw(t))+1)$ for WEnKI, WEnSRF and IS

Table 1.  Error of moments estimation in Example 3

 WEnKI WEnSRF Moments Est. Re. Error Est. Re. Error $\mathbb{E}|u|^1=3.84$ 3.82 0.0056 3.88 0.0098 $\mathbb{E}|u|^2=14.90$ 14.73 0.0114 15.19 0.0192 $\mathbb{E}|u|^3=58.22$ 57.19 0.0177 59.86 0.0281 $\mathbb{E}|u|^4=229.36$ 223.79 0.0243 237.75 0.0366 $\mathbb{E}|u|^5=911.22$ 882.83 0.0312 951.95 0.0447 EnKI EnSRF Moments Est. Re. Error Est. Re. Error $\mathbb{E}|u|^1=3.84$ 3.69 0.0413 3.70 0.0391 $\mathbb{E}|u|^2=14.90$ 13.66 0.0833 13.73 0.0785 $\mathbb{E}|u|^3=58.22$ 50.90 0.1258 51.35 0.1181 $\mathbb{E}|u|^4=229.36$ 190.68 0.1687 193.24 0.1575 $\mathbb{E}|u|^5=911.22$ 718.31 0.2117 732.17 0.1965 WEnKF IS Moments Est. Re. Error Est. Re. Error $\mathbb{E}|u|^1=3.84$ 3.40 0.1156 3.52 0.0858 $\mathbb{E}|u|^2=14.90$ 11.65 0.2181 12.37 0.1699 $\mathbb{E}|u|^3=58.22$ 40.22 0.3093 43.57 0.2517 $\mathbb{E}|u|^4=229.36$ 139.72 0.3908 153.56 0.3305 $\mathbb{E}|u|^5=911.22$ 488.51 0.4639 541.71 0.4055

Table 2.  Simulation time in Example 1-3

 Case WEnKI WEnSRF EnKI EnSRF Example 1 0.362s 0.197s 0.138s 0.178s Example 2 50.041s 41.739s 26.564s 18.518s Example 3 0.198s 0.115s 0.120s 0.072s

Table 3.  Error of moments estimation in Example 5

 WEnKI WEnSRF Moments Est. Re. Error Est. Re. Error $\mathbb{E}|u|^1=3.32$ 3.30 0.0055 3.32 0.0017 $\mathbb{E}|u|^2=11.16$ 10.99 0.0147 11.19 0.0023 $\mathbb{E}|u|^3=38.05$ 36.99 0.0279 38.12 0.0019 $\mathbb{E}|u|^4=131.45$ 125.53 0.0451 131.47 0.0001 $\mathbb{E}|u|^5=460.56$ 429.99 0.0664 459.16 0.0030 EnKI EnSRF Moments Est. Re. Error Est. Re. Error $\mathbb{E}|u|^1=3.32$ 2.96 0.1084 3.28 0.0112 $\mathbb{E}|u|^2=11.16$ 9.07 0.1872 11.04 0.0111 $\mathbb{E}|u|^3=38.05$ 29.17 0.2332 38.25 0.0053 $\mathbb{E}|u|^4=131.45$ 100.32 0.2369 137.43 0.0455 $\mathbb{E}|u|^5=460.56$ 379.73 0.1755 516.22 0.1208 WEnKF IS Moments Est. Re. Error Est. Re. Error $\mathbb{E}|u|^1=3.32$ 3.40 0.1658 3.24 0.0245 $\mathbb{E}|u|^2=11.16$ 7.72 0.3077 10.50 0.0592 $\mathbb{E}|u|^3=38.05$ 21.74 0.4287 34.10 0.1037 $\mathbb{E}|u|^4=131.45$ 61.62 0.5313 110.81 0.1571 $\mathbb{E}|u|^5=460.56$ 175.99 0.6179 360.27 0.2178
•  [1] C. Andrieu, N. Freitas, A. Doucet and M. Jordan, An introduction to MCMC for machine learning, Machine Learning, 50 (2003), 5-43. [2] A. Bain and D. Crisan, Fundamentals of Stochastic Filtering, Stochastic Modelling and Applied Probability, Springer New York, 2008. doi: 10.1007/978-0-387-76896-0. [3] K. Bergemann and S. Reich, A localization technique for ensemble Kalman filters, Quarterly Journal of the Royal Meteorological Society, 136 (2010), 701-707.  doi: 10.1002/qj.591. [4] K. Bergemann and S. Reich, A mollified ensemble Kalman filter, Quarterly Journal of the Royal Meteorological Society, 136 (2010), 1636-1643.  doi: 10.1002/qj.672. [5] D. Blömker, C. Schillings, P. Wacker and S. Weissmann, Well posedness and convergence analysis of the ensemble Kalman inversion, Inverse Problems, 35 (2019), 085007. doi: 10.1088/1361-6420/ab149c. [6] D. Blomker, C. Schillings and P. Wacker, A strongly convergent numerical scheme from ensemble Kalman inversion, SIAM Journal on Numerical Analysis, 56 (2018), 2537-2562.  doi: 10.1137/17M1132367. [7] J. A. Cañizo, J. A. Carrillo and J. Rosado, A well-posedness theory in measures for some kinetic models of collective motion, Mathematical Models and Methods in Applied Sciences, 21 (2011), 515-539.  doi: 10.1142/S0218202511005131. [8] N. Chada, A. Stuart and X. Tong, Tikhonov regularization within ensemble Kalman inversion, SIAM Journal on Numerical Analysis, 58 (2019), 1263-1294.  doi: 10.1137/19M1242331. [9] N. Chada and X. T. Tong, Convergence acceleration of ensemble Kalman inversion in nonlinear settings, preprint, arXiv: 1911.02424. [10] N. K. Chada, M. A. Iglesias, L. Roininen and A. M. Stuart, Parameterizations for ensemble kalman inversion, Inverse Problems, 34 (2018), 055009. doi: 10.1088/1361-6420/aab6d9. [11] 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. [12] Z. Ding and Q. Li, Ensemble Kalman inversion: Mean-field limit and convergence analysis, arXiv: 1908.05575. [13] Z. Ding and Q. Li, Ensemble Kalman sampling: Mean-field limit and convergence analysis, preprint, arXiv: 1910.12923. [14] A. Doucet, N. De Freitas and N. Gordon, An Introduction to Sequential Monte Carlo Methods, Springer New York, New York, NY, 2001. doi: 10.1007/978-1-4757-3437-9_1. [15] A. Doucet, N. De Freitas and N. Gordon, Sequential Monte Carlo Methods in Practice, Springer New York, London, 2001. doi: 10.1007/978-1-4757-3437-9. [16] O. G. Ernst, B. Sprungk and H.-J. 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. [17] G. Evensen, Data Assimilation: The Ensemble Kalman Filter, Springer-Verlag, Berlin, Heidelberg, 2006. doi: 10.1007/978-3-642-03711-5. [18] N. Fournier and A. Guillin, On the rate of convergence in Wasserstein distance of the empirical measure, Probability Theory and Related Fields, 162 (2015), 707-738.  doi: 10.1007/s00440-014-0583-7. [19] A. Garbuno-Inigo, F. Hoffmann, W. Li and A. M. Stuart, Interacting Langevin diffusions: Gradient structure and ensemble Kalman sampler, SIAM Journal on Applied Dynamical Systems, 19 (2020), 412-441.  doi: 10.1137/19M1251655. [20] A. Garbuno-Inigo, N. Nüsken and S. Reich, Affine invariant interacting Langevin dynamics for Bayesian inference, CoRR, abs/1912.02859. [21] J. Geweke, Bayesian inference in econometric models using Monte Carlo integration, Econometrica, 57 (1989), 1317-1339.  doi: 10.2307/1913710. [22] M. Herty and G. Visconti, Continuous limits for constrained ensemble Kalman filter, Inverse Problems, 36 (2020), 075006. doi: 10.1088/1361-6420/ab8bc5. [23] M. A. Iglesias, K. J. H. Law and A. M. Stuart, Ensemble Kalman methods for inverse problems, Inverse Problems, 29 (2013), 045001. doi: 10.1088/0266-5611/29/4/045001. [24] T. Lange and W. Stannat, On the continuous time limit of the ensemble Kalman filter, preprint, arXiv: 1901.05204. doi: 10.1090/mcom/3588. [25] K. J. H. Law, H. Tembine and R. Tempone, Deterministic mean-field ensemble Kalman filtering, SIAM Journal on Scientific Computing, 38 (2016), A1251–A1279. doi: 10.1137/140984415. [26] D. M. Livings, S. L. Dance and N. K. Nichols, Unbiased ensemble square root filters, Physica D: Nonlinear Phenomena, 237 (2008), 1021-1028.  doi: 10.1016/j.physd.2008.01.005. [27] Y. Lu, J. Lu and J. Nolen, Accelerating Langevin sampling with birth-death, preprint, arXiv: 1905.09863. [28] J. Martin, L. Wilcox, C. Burstedde and O. Ghattas, A stochastic newton MCMC method for large-scale statistical inverse problems with application to seismic inversion, SIAM Journal on Scientific Computing, 34 (2012), A1460–A1487. doi: 10.1137/110845598. [29] Y. M. Marzouk, H. N. Najm and L. A. Rahn, Stochastic spectral methods for efficient Bayesian solution of inverse problems, Journal of Computational Physics, 224 (2007), 560-586.  doi: 10.1016/j.jcp.2006.10.010. [30] A. Muntean, J. Rademacher and A. Zagaris, Macroscopic and Large Scale Phenomena: Coarse Graining, Mean Field Limits and Ergodicity, LAMM, 3, Springer, Cham, 2016. doi: 10.1007/978-3-319-26883-5. [31] N. Papadakis, E. Mémin, A. Cuzol and N. Gengembre, Data assimilation with the weighted ensemble Kalman filter, Tellus A, 62 (2010), 673-697. [32] S. Reich, A dynamical systems framework for intermittent data assimilation, BIT Numerical Mathematics, 51 (2011), 235-249.  doi: 10.1007/s10543-010-0302-4. [33] S. Reich and  C. Cotter,  Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, 2015.  doi: 10.1017/CBO9781107706804. [34] S. Reich and S. Weissmann, Fokker-planck particle systems for bayesian inference: Computational approaches, preprint, arXiv: 1911.10832. [35] C. Schillings and A. M. Stuart, Analysis of the ensemble Kalman filter for inverse problems, SIAM Journal on Numerical Analysis, 55 (2017), 1264-1290.  doi: 10.1137/16M105959X. [36] M. Tippett, J. Anderson, C. Bishop, T. Hamill and J. Whitaker, Ensemble square root filters, Monthly Weather Review, 131 (2003), 1485-1490.  doi: 10.1175/1520-0493(2003)131<1485:ESRF>2.0.CO;2.

Figures(7)

Tables(3)