Iterative ensemble Kalman methods: A unified perspective with some new variants

Neil K. Chada; Yuming Chen; Daniel Sanz-Alonso

doi:10.3934/fods.2021011

Article Contents

2021, Volume 3, Issue 3: 331-369. Doi: 10.3934/fods.2021011

This issue Previous Article Online learning of both state and dynamics using ensemble Kalman filters Next Article Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds

Iterative ensemble Kalman methods: A unified perspective with some new variants

1.
Applied Mathematics and Computational Science, King Abdullah University of Science and Technology, Thuwal, 23955, Saudi Arabia
2.
Department of Statistics, University of Chicago, Chicago, IL 60637, USA

^* Corresponding author: Daniel Sanz-Alonso
^* Corresponding author: Daniel Sanz-Alonso

Received: October 2020

Revised: January 2021

Early access: April 2021

Published: September 2021

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

Abstract / Introduction Full Text(HTML) Figure(14) / Table(2) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 37C10, 60G35; Secondary: 65N20.

Citation:

Full Text(HTML)

Figure 1. Ensemble members (green) after $ 100 $ iterations, with truth $ u^\dagger $ (red star) and contour plot of (unnormalized) posterior density

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 3. EKI & EKI-SL: Relative errors and data misfit w.r.t time $ t $

Download: Full-size image PowerPoint slide

Figure 4. TEKI, IEKF & IEKF-SL: Relative errors and Tikhonov-Phillips objective w.r.t time $ t $

Download: Full-size image PowerPoint slide

Figure 5. Ensemble mean (red) at the final iteration, with 10, 90-quantiles (blue)

Download: Full-size image PowerPoint slide

Figure 6. EKI & EKI-SL: Relative errors and data misfit w.r.t time $ t $

Download: Full-size image PowerPoint slide

Figure 7. IEKF, TEKI & IEKF-SL: Relative errors and Tikhonov-Phillips objective w.r.t time $ t $

Download: Full-size image PowerPoint slide

Figure 8. Ensemble mean (red) at the final iteration, with 10, 90-quantiles (blue)

Download: Full-size image PowerPoint slide

Figure 9. EKI & EKI-SL: Relative errors and data misfit w.r.t time $ t $

Download: Full-size image PowerPoint slide

Figure 10. IEKF, TEKI & IEKF-SL: Relative errors and Tikhonov-Phillips objective w.r.t time $ t $

Download: Full-size image PowerPoint slide

Figure 11. Tikhonov-Phillips objective function with respect to two randomly chosen coordinates

Download: Full-size image PowerPoint slide

Figure 12. Ensemble mean (red) at the final iteration, with 10, 90-quantiles (blue)

Download: Full-size image PowerPoint slide

Figure 13. EKI & EKI-SL: Relative errors and data misfit w.r.t time $ t $

Download: Full-size image PowerPoint slide

Figure 14. IEKF, TEKI & IEKF-SL: Relative errors and Tikhonov-Phillips objective w.r.t time $ t $

Download: Full-size image PowerPoint slide

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)

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	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.
[2]	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.
[3]	B. D. O. Anderson and J. B. Moore, Optimal Filtering, Information and System Sciences Series, (1979).
[4]	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.
[5]	B. M. Bell, The iterated Kalman smoother as a Gauss-Newton method, SIAM J. Optim., 4 (1994), 626-636. doi: 10.1137/0804035.
[6]	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.
[7]	D. P. Bertsakas, Incremental least squares method and the extended Kalman filter, SIAM J. Optim, 6 (1996), 807-822. doi: 10.1137/S1052623494268522.
[8]	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.
[9]	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.
[10]	N. K. Chada, Analysis of hierarchical ensemble Kalman inversion, preprint, arXiv: 1801.00847.
[11]	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.
[12]	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.
[13]	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.
[14]	N. K. Chada and X. T. Tong, Convergence acceleration of ensemble Kalman inversion in nonlinear settings, preprint, arXiv: 1911.02424.
[15]	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.
[16]	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.
[17]	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.
[18]	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.
[19]	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.
[20]	G. Evensen, Data Assimilation. The Ensemble Kalman Filter, Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-642-03711-5.
[21]	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.
[22]	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.
[23]	I. Grooms, A note on the formulation of the Ensemble Adjustment Kalman Filter, preprint, arXiv: 2006.02941.
[24]	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.
[25]	P. A. Guth, C. Schillings and S. Weissmann, Ensemble Kalman filter for neural network based one-shot inversion, preprint, arXiv: 2005.02039.
[26]	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.
[27]	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.
[28]	M. Herty and G. Visconti, Kinetic methods for inverse problems, Kinet. Relat. Models, 12 (2019), 1109-1130. doi: 10.3934/krm.2019042.
[29]	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.
[30]	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.
[31]	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.
[32]	M. A. Iglesias and Y. Yang, Adaptive regularisation for ensemble Kalman inversion, Inverse Problems, 37 (2021), 40pp. doi: 10.1088/1361-6420/abd29b.
[33]	A. H. Jazwinski, Stochastic Processes and Filtering Theory, Courier Corporation, 2007.
[34]	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.
[35]	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.
[36]	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.
[37]	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.
[38]	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.
[39]	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.
[40]	Y. Lee, $l_p$ regularization for ensemble Kalman inversion, preprint, arXiv: 2009.03470.
[41]	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.
[42]	A. C. Lorenc, Analysis methods for numerical weather prediction, Quart. J. Roy. Meteor. Soc., 112 (1986), 1177-1194. doi: 10.1002/qj.49711247414.
[43]	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.
[44]	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.
[45]	A. J. Madja and J. Harlim, Filtering Complex Turbulent Systems, Cambridge University Press, Cambridge, 2012. doi: 10.1017/CBO9781139061308.
[46]	J. Mandel, E. Bergou and S. Gratton, 4DVAR by ensemble Kalman smoother, preprint, arXiv: 1304.5271.
[47]	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.
[48]	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.
[49]	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.
[50]	D. Oliver, A. C. Reynolds and N. Liu, Inverse Theory for Petroleum Reservoir Characterization and History Matching, Cambridge University Press, 2008.
[51]	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.
[52]	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.
[53]	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.
[54]	D. Sanz-Alonso, A. Stuart and A. Taeb, Data assimilation and inverse problems, preprint, arXiv: 1810.06191.
[55]	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.
[56]	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.
[57]	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.
[58]	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.
[59]	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.
[60]	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.
[61]	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.
[62]	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.
[63]	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.
[64]	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.