Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds
FoDS Home
Online learning of both state and dynamics using ensemble Kalman filters
September 2021, 3(3): 331-369. doi: 10.3934/fods.2021011
Iterative ensemble Kalman methods: A unified perspective with some new variants
Neil K. Chada 1, , Yuming Chen 2, and Daniel Sanz-Alonso 2,,
Applied Mathematics and Computational Science, King Abdullah University of Science and Technology, Thuwal, 23955, Saudi Arabia
Department of Statistics, University of Chicago, Chicago, IL 60637, USA
* Corresponding author: Daniel Sanz-Alonso
Received October 2020 Revised January 2021 Published September 2021 Early access April 2021
Fund Project: NKC is supported by KAUST baseline funding. DSA is thankful for the support of NSF and NGA through the grant DMS-2027056. The work of DSA was also partially supported by the NSF Grant DMS-1912818/1912802
Figure(14) / Table(2)
This paper provides a unified perspective of iterative ensemble Kalman methods, a family of derivative-free algorithms for parameter reconstruction and other related tasks. We identify, compare and develop three subfamilies of ensemble methods that differ in the objective they seek to minimize and the derivative-based optimization scheme they approximate through the ensemble. Our work emphasizes two principles for the derivation and analysis of iterative ensemble Kalman methods: statistical linearization and continuum limits. Following these guiding principles, we introduce new iterative ensemble Kalman methods that show promising numerical performance in Bayesian inverse problems, data assimilation and machine learning tasks.
Keywords: Ensemble Kalman methods, inverse problems, statistical linearization, continuum limits.
Mathematics Subject Classification: Primary: 37C10, 60G35; Secondary: 65N20.
Citation: Neil K. Chada, Yuming Chen, Daniel Sanz-Alonso. Iterative ensemble Kalman methods: A unified perspective with some new variants. Foundations of Data Science, 2021, 3 (3) : 331-369. doi: 10.3934/fods.2021011
S. I. Aanonsen, G. Nævdal, D. S. Oliver, A. C. Reynolds and B. Vallès, The ensemble Kalman filter in reservoir engineering-A review, SPE J., 14 (2009), 393-412. doi: 10.2118/117274-PA. Google Scholar
D. J. Albers, P.-A. Blancquart, M. E. Levine, E. Esmaeilzadeh Seylabi and A. Stuart, Ensemble Kalman methods with constraints, Inverse Problems, 35 (2019), 28pp. doi: 10.1088/1361-6420/ab1c09. Google Scholar
B. D. O. Anderson and J. B. Moore, Optimal Filtering, Information and System Sciences Series, (1979). Google Scholar
J. L. Anderson, An ensemble adjustment Kalman filter for data assimilation, Monthly Weather Review, 129 (2001), 2884-2903. doi: 10.1175/1520-0493(2001)129<2884:AEAKFF>2.0.CO;2. Google Scholar
B. M. Bell, The iterated Kalman smoother as a Gauss-Newton method, SIAM J. Optim., 4 (1994), 626-636. doi: 10.1137/0804035. Google Scholar
B. M. Bell and F. W. Cathey, The iterated Kalman filter update as a Gauss-Newton method, IEEE Trans. Automat. Control, 38 (1993), 294-297. doi: 10.1109/9.250476. Google Scholar
D. P. Bertsakas, Incremental least squares method and the extended Kalman filter, SIAM J. Optim, 6 (1996), 807-822. doi: 10.1137/S1052623494268522. Google Scholar
D. Blömker, C. Schillings and P. Wacker, A strongly convergent numerical scheme from ensemble Kalman inversion, SIAM J. Numer. Anal., 56 (2018), 2537-2562. doi: 10.1137/17M1132367. Google Scholar
D. Blömker, C. Schillings, P. Wacker and S. Weissmann, Well posedness and convergence analysis of the ensemble Kalman inversion, Inverse Problems, 35 (2019), 32pp. doi: 10.1088/1361-6420/ab149c. Google Scholar
N. K. Chada, Analysis of hierarchical ensemble Kalman inversion, preprint, arXiv: 1801.00847. Google Scholar
N. K. Chada, M. A. Iglesias, L. Roininen and A. M. Stuart, Parameterizations for ensemble Kalman inversion, Inverse Problems, 34 (2018), 31pp. doi: 10.1088/1361-6420/aab6d9. Google Scholar
N. K. Chada, C. Schillings and S. Weissmann, On the incorporation of box-constraints for ensemble Kalman inversion, Foundations of Data Science, 1 (2019), 433-456. doi: 10.3934/fods.2019018. Google Scholar
N. K. Chada, A. M. Stuart and X. T. Tong, Tikhonov regularization within ensemble Kalman inversion, SIAM J. Numer. Anal., 58 (2020), 1263-1294. doi: 10.1137/19M1242331. Google Scholar
N. K. Chada and X. T. Tong, Convergence acceleration of ensemble Kalman inversion in nonlinear settings, preprint, arXiv: 1911.02424. Google Scholar
Y. Chen and D. S. Oliver, Ensemble randomized maximum likelihood method as an iterative ensemble smoother, Mathematical Geosciences, 44 (2012), 1-26. doi: 10.1007/s11004-011-9376-z. Google Scholar
J. E. Dennis Jr. and R. B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Classics in Applied Mathematics, 16, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. doi: 10.1137/1.9781611971200. Google Scholar
Z. Ding and Q. Li, Ensemble Kalman sampler: Mean-field limit and convergence analysis, SIAM J. Math. Anal., 53 (2021), 1546-1578. doi: 10.1137/20M1339507. Google Scholar
A. A. Emerick and A. C. Reynolds, Ensemble smoother with multiple data assimilation, Computers & Geosciences, 55 (2013), 3-15. doi: 10.1016/j.cageo.2012.03.011. Google Scholar
O. G. Ernst, B. Sprungk and H.-J. Starkloff, Analysis of the ensemble and polynomial chaos Kalman filters in Bayesian inverse problems, SIAM/ASA J. Uncertain. Quantif., 3 (2015), 823-851. doi: 10.1137/140981319. Google Scholar
G. Evensen, Data Assimilation. The Ensemble Kalman Filter, Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-642-03711-5. Google Scholar
G. Evensen and P. J. Van Leeuwen, Assimilation of geosat altimeter data for the Agulhas current using the ensemble Kalman filter with a quasigeostrophic model, Monthly Weather Review, 124 (1996), 85-96. doi: 10.1175/1520-0493(1996)124<0085:AOGADF>2.0.CO;2. Google Scholar
A. Garbuno-Inigo, F. Hoffmann, W. Li and A. M. Stuart, Interacting Langevin diffusions: Gradient structure and ensemble Kalman sampler, SIAM J. Appl. Dyn. Syst., 19 (2020), 412-441. doi: 10.1137/19M1251655. Google Scholar
I. Grooms, A note on the formulation of the Ensemble Adjustment Kalman Filter, preprint, arXiv: 2006.02941. Google Scholar
Y. Gu and D. S. Oliver, An iterative ensemble Kalman filter for multiphase fluid flow data assimilation, Spe Journal, 12 (2007), 438-446. doi: 10.2118/108438-PA. Google Scholar
P. A. Guth, C. Schillings and S. Weissmann, Ensemble Kalman filter for neural network based one-shot inversion, preprint, arXiv: 2005.02039. Google Scholar
E. Haber, F. Lucka and L. Ruthotto, Never look back - A modified EnKF method and its application to the training of neural networks without back propagation, preprint, arXiv: 1805.08034. Google Scholar
M. Hanke, A regularizing Levenberg-Marquardt scheme, with applications to inverse groundwater filtration problems, Inverse Problems, 13 (1997), 79-95. doi: 10.1088/0266-5611/13/1/007. Google Scholar
M. Herty and G. Visconti, Kinetic methods for inverse problems, Kinet. Relat. Models, 12 (2019), 1109-1130. doi: 10.3934/krm.2019042. Google Scholar
M. A. Iglesias, A regularising iterative ensemble Kalman method for PDE-constrained inverse problems, Inverse Problems, 32 (2016), 45pp. doi: 10.1088/0266-5611/32/2/025002. Google Scholar
M. A. Iglesias, K. J. H. Law and A. M. Stuart, Ensemble Kalman methods for inverse problems, Inverse Problems, 29 (2013), 20pp. doi: 10.1088/0266-5611/29/4/045001. Google Scholar
M. A. Iglesias, K. Lin, S. Lu and A. M. Stuart, Filter based methods for statistical linear inverse problems, Commun. Math. Sci., 15 (2017), 1867-1895. doi: 10.4310/CMS.2017.v15.n7.a4. Google Scholar
M. A. Iglesias and Y. Yang, Adaptive regularisation for ensemble Kalman inversion, Inverse Problems, 37 (2021), 40pp. doi: 10.1088/1361-6420/abd29b. Google Scholar
A. H. Jazwinski, Stochastic Processes and Filtering Theory, Courier Corporation, 2007. Google Scholar
R. E. Kalman, A new approach to linear filtering and prediction problems, Trans. ASME Ser. D. J. Basic Engrg., 82 (1960), 35-45. doi: 10.1115/1.3662552. Google Scholar
E. Kalnay, S. K. Park, Z.-X. Pu and J. Gao, Application of the quasi-inverse method to data assimilation, Monthly Weather Review, 128 (2000), 864-875. doi: 10.1175/1520-0493(2000)128<0864:AOTQIM>2.0.CO;2. Google Scholar
B. Katltenbacher, A. Neubauer and O. Scherzer, Iterative Regularization Methods for Nonlinear Ill-Posed Problems, Radon Series on Computational and Applied Mathematics, 6, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. doi: 10.1515/9783110208276. 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-5604. doi: 10.1088/0951-7715/27/10/2579. Google Scholar
N. B. Kovachki and A. M. Stuart, Ensemble Kalman inversion: A derivative-free technique for machine learning tasks, Inverse Problems, 35 (2019), 35pp. doi: 10.1088/1361-6420/ab1c3a. Google Scholar
W. G. Lawson and J. A. Hansen, Implications of stochastic and deterministic filters as ensemble-based data assimilation methods in varying regimes of error growth, Monthly Weather Review, 132 (2004), 1966-1981. doi: 10.1175/1520-0493(2004)132<1966:IOSADF>2.0.CO;2. Google Scholar
Y. Lee, $l_p$ regularization for ensemble Kalman inversion, preprint, arXiv: 2009.03470. Google Scholar
G. Li and A. C. Reynolds, An iterative ensemble Kalman filter for data assimilation, SPE Annual Technical Conference and Exhibition, Society of Petroleum Engineers, Anaheim, CA, 2007. doi: 10.2118/109808-MS. Google Scholar
A. C. Lorenc, Analysis methods for numerical weather prediction, Quart. J. Roy. Meteor. Soc., 112 (1986), 1177-1194. doi: 10.1002/qj.49711247414. Google Scholar
R. J. Lorentzen, K.-K. Fjelde, J. Froyen, A. C. V. M. Lage, G. Nævdal and E. H. Vefring, Underbalanced drilling: Real time data interpretation and decision support, SPE/IADC Drilling Conference, Amsterdam, Netherlands, 2001. doi: 10.2118/67693-MS. Google Scholar
S. Lu and S. V. Pereverzev, Multi-parameter regularization and its numerical realization, Numer. Math., 118 (2001), 1-31. doi: 10.1007/s00211-010-0318-3. Google Scholar
A. J. Madja and J. Harlim, Filtering Complex Turbulent Systems, Cambridge University Press, Cambridge, 2012. doi: 10.1017/CBO9781139061308. Google Scholar
J. Mandel, E. Bergou and S. Gratton, 4DVAR by ensemble Kalman smoother, preprint, arXiv: 1304.5271. Google Scholar
G. Nævdal, T. Mannseth and E. H Vefring, Instrumented wells and near-well reservoir monitoring through ensemble Kalman filter, Proceedings of 8th European Conference on the Mathematics of Oil Recovery, Freiberg, Germany, 2001. Google Scholar
A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. Google Scholar
J. Nocedal and S. J. Wright, Numerical Optimization, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. doi: 10.1007/978-0-387-40065-5. Google Scholar
D. Oliver, A. C. Reynolds and N. Liu, Inverse Theory for Petroleum Reservoir Characterization and History Matching, Cambridge University Press, 2008. Google Scholar
S. Reich and C. J. Cotter, Ensemble filter techniques for intermittent data assimilation, in Large Scale Inverse Problems, Radon Ser. Comput. Appl. Math., 13, De Gruyter, Berlin, 2013, 91-134. doi: 10.1515/9783110282269.91. Google Scholar
A. C. Reynolds, M. Zafari and G. Li, Iterative forms of the ensemble Kalman filter, ECMOR X-10th European Conference on the Mathematics of Oil Recovery, 2006. doi: 10.3997/2214-4609.201402496. Google Scholar
P. Sakov, D. S. Oliver and L. Bertino, An Iterative EnKF for strongly nonlinear systems, Monthly Weather Review, 140 (2012), 1988-2004. doi: 10.1175/MWR-D-11-00176.1. Google Scholar
D. Sanz-Alonso, A. Stuart and A. Taeb, Data assimilation and inverse problems, preprint, arXiv: 1810.06191. Google Scholar
C. Schillings and A. M. Stuart, Analysis of the ensemble Kalman filter for inverse problems, SIAM J. Numer. Anal., 55 (2017), 1264-1290. doi: 10.1137/16M105959X. Google Scholar
C. Schillings and A. M. Stuart, Convergence analysis of ensemble Kalman inversion: The linear, noisy case, Appl. Anal., 97 (2018), 107-123. doi: 10.1080/00036811.2017.1386784. Google Scholar
T. Schneider, A. M. Stuart and J.-L. Wu, Ensemble Kalman inversion for sparse learning of dynamical systems from time-averaged data, preprint, arXiv: 2007.06175. Google Scholar
B. Shi, S. S. Du, M. I. Jordan and W. J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, preprint, arXiv: 1810.08907. Google Scholar
J. A. Skjervheim, G. Evensen, J. Hove and J. G. Vabø, An ensemble smoother for assisted history matching, SPE Reservoir Simulation Symposium, The Woodlands, TX, 2001. doi: 10.2118/141929-MS. Google Scholar
W. Su, S. Boyd and E. J. Candès, A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights, J. Mach. Learn. Res., 17 (2016), 43pp. Google Scholar
A. Tarantola, Inverse Problem Theory and Methods for Model Parameter Estimation, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. doi: 10.1137/1.9780898717921. Google Scholar
M. K. Tippett, J. L. Anderson, C. H. Bishop, T. M. Hamill and J. S. 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. Google Scholar
S. Ungarala, On the iterated forms of Kalman filters using statistical linearization, J. Process Control, 22 (2012), 935-943. doi: 10.1016/j.jprocont.2012.03.004. Google Scholar
A. Wibisono, A. C. Wilson and M. I. Jordan, A variational perspective on accelerated methods in optimization, Proc. Natl. Acad. Sci. USA, 113 (2016), E7351-E7358. doi: 10.1073/pnas.1614734113. Google Scholar
Figure 1. Ensemble members (green) after $ 100 $ iterations, with truth $ u^\dagger $ (red star) and contour plot of (unnormalized) posterior density
Figure 2. Evolution of the Frobenius norm of the ensemble covariance $ P^{uu}(t) $. For reference, we also plot the Frobenius norm of the true posterior covariance (red dashed line). The norm of IEKF-RZL blows up after a few iterations. The norms of the EKI and TEKI are almost identical and monotonically decreasing. The norms of the new variants EKI-SL and IEKF-SL are similar and stabilize after around 40 iterations. The norm of IEKF lies between those of the old and new variants
Figure 3. EKI & EKI-SL: Relative errors and data misfit w.r.t time $ t $
Figure 4. TEKI, IEKF & IEKF-SL: Relative errors and Tikhonov-Phillips objective w.r.t time $ t $
Figure 5. Ensemble mean (red) at the final iteration, with 10, 90-quantiles (blue)
Figure 7. IEKF, TEKI & IEKF-SL: Relative errors and Tikhonov-Phillips objective w.r.t time $ t $
Figure 10. IEKF, TEKI & IEKF-SL: Relative errors and Tikhonov-Phillips objective w.r.t time $ t $
Figure 11. Tikhonov-Phillips objective function with respect to two randomly chosen coordinates
Figure 12. Ensemble mean (red) at the final iteration, with 10, 90-quantiles (blue)
Figure 13. EKI & EKI-SL: Relative errors and data misfit w.r.t time $ t $
Table 1. Roadmap to the algorithms considered in this paper. We use the abbreviations GN and LM for Gauss-Newton and Levenberg-Marquardt. The numbers in parenthesis represent the subsection in which each algorithm is introduced
Objective Optimization Derivative Method Ensemble Method New Variant
$ {\mathtt{J}}_{\text{TP}} $ GN IExKF (2.1) IEKF (3.1) IEKF-SL (4.1)
$ {\mathtt{J}}_{\text{DM}} $ LM LM-DM (2.2) EKI (3.2) EKI-SL (4.2)
$ {\mathtt{J}}_{\text{TP}} $ LM LM-TP (2.3) TEKI (3.3) TEKI-SL (4.3)
Table Options
Table 2. Summary of the main algorithms in Sections 2 and 3
Objective Optimization Derivative Method Ensemble Method
$ {\mathtt{J}}_{\text{TP}} $ GN IExKF IEKF
$ {\mathtt{J}}_{\text{DM}} $ LM ILM-DM EKI
$ {\mathtt{J}}_{\text{TP}} $ LM ILM-TP TEKI
Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2021, 3 (3) : 371-411. doi: 10.3934/fods.2020018
Michael Herty, Giuseppe Visconti. Kinetic methods for inverse problems. Kinetic & Related Models, 2019, 12 (5) : 1109-1130. doi: 10.3934/krm.2019042
Lili Ju, Wei Leng, Zhu Wang, Shuai Yuan. Numerical investigation of ensemble methods with block iterative solvers for evolution problems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (12) : 4905-4923. doi: 10.3934/dcdsb.2020132
Neil K. Chada, Claudia Schillings, Simon Weissmann. On the incorporation of box-constraints for ensemble Kalman inversion. Foundations of Data Science, 2019, 1 (4) : 433-456. doi: 10.3934/fods.2019018
Andreas Bock, Colin J. Cotter. Learning landmark geodesics using the ensemble Kalman filter. Foundations of Data Science, 2021, 3 (4) : 701-727. doi: 10.3934/fods.2021020
Abhishake Rastogi. Tikhonov regularization with oversmoothing penalty for nonlinear statistical inverse problems. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4111-4126. doi: 10.3934/cpaa.2020183
Tapio Helin. On infinite-dimensional hierarchical probability models in statistical inverse problems. Inverse Problems & Imaging, 2009, 3 (4) : 567-597. doi: 10.3934/ipi.2009.3.567
Martin Hanke, William Rundell. On rational approximation methods for inverse source problems. Inverse Problems & Imaging, 2011, 5 (1) : 185-202. doi: 10.3934/ipi.2011.5.185
Daijun Jiang, Hui Feng, Jun Zou. Overlapping domain decomposition methods for linear inverse problems. Inverse Problems & Imaging, 2015, 9 (1) : 163-188. doi: 10.3934/ipi.2015.9.163
Paolo Podio-Guidugli. On the modeling of transport phenomena in continuum and statistical mechanics. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1393-1411. doi: 10.3934/dcdss.2017074
Junyoung Jang, Kihoon Jang, Hee-Dae Kwon, Jeehyun Lee. Feedback control of an HBV model based on ensemble kalman filter and differential evolution. Mathematical Biosciences & Engineering, 2018, 15 (3) : 667-691. doi: 10.3934/mbe.2018030
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
Jiangqi Wu, Linjie Wen, Jinglai Li. Resampled ensemble Kalman inversion for Bayesian parameter estimation with sequential data. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021045
Le Yin, Ioannis Sgouralis, Vasileios Maroulas. Topological reconstruction of sub-cellular motion with Ensemble Kalman velocimetry. Foundations of Data Science, 2020, 2 (2) : 101-121. doi: 10.3934/fods.2020007
Marc Bocquet, Alban Farchi, Quentin Malartic. Online learning of both state and dynamics using ensemble Kalman filters. Foundations of Data Science, 2021, 3 (3) : 305-330. doi: 10.3934/fods.2020015
Sari Lasanen. Non-Gaussian statistical inverse problems. Part II: Posterior convergence for approximated unknowns. Inverse Problems & Imaging, 2012, 6 (2) : 267-287. doi: 10.3934/ipi.2012.6.267
Sari Lasanen. Non-Gaussian statistical inverse problems. Part I: Posterior distributions. Inverse Problems & Imaging, 2012, 6 (2) : 215-266. doi: 10.3934/ipi.2012.6.215
Claudio Canuto, Anna Cattani. The derivation of continuum limits of neuronal networks with gap-junction couplings. Networks & Heterogeneous Media, 2014, 9 (1) : 111-133. doi: 10.3934/nhm.2014.9.111
Alexey Penenko. Convergence analysis of the adjoint ensemble method in inverse source problems for advection-diffusion-reaction models with image-type measurements. Inverse Problems & Imaging, 2020, 14 (5) : 757-782. doi: 10.3934/ipi.2020035
Lijian Jiang, Yalchin Efendiev, Victor Ginting. Multiscale methods for parabolic equations with continuum spatial scales. Discrete & Continuous Dynamical Systems - B, 2007, 8 (4) : 833-859. doi: 10.3934/dcdsb.2007.8.833
Neil K. Chada Yuming Chen Daniel Sanz-Alonso