Hierarchical ensemble Kalman methods with sparsity-promoting generalized gamma hyperpriors

Hwanwoo Kim; Daniel Sanz-Alonso; Alexander Strang

doi:10.3934/fods.2023003

Article Contents

2023, Volume 5, Issue 3: 366-388. Doi: 10.3934/fods.2023003

This issue Previous Article Unsupervised learning of observation functions in state space models by nonparametric moment methods Next Article Normalization effects on deep neural networks

Hierarchical ensemble Kalman methods with sparsity-promoting generalized gamma hyperpriors

1.
University of Chicago, USA

^*Corresponding author: Hwanwoo Kim
^*Corresponding author: Hwanwoo Kim

Received: November 2022

Revised: January 2023

Early access: March 2023

Published: September 2023

Abstract / Introduction Full Text(HTML) Figure(7) / Table(4) Related Papers Cited by

Abstract

This paper introduces a computational framework to incorporate flexible regularization techniques in ensemble Kalman methods, generalizing the iterative alternating scheme to nonlinear inverse problems. The proposed methodology approximates the maximum a posteriori (MAP) estimate of a hierarchical Bayesian model characterized by a conditionally Gaussian prior and generalized gamma hyperpriors. Suitable choices of hyperparameters yield sparsity-promoting regularization. We propose an iterative algorithm for MAP estimation, which alternates between updating the unknown with an ensemble Kalman method and updating the hyperparameters in the regularization to promote sparsity. The effectiveness of our methodology is demonstrated in several computed examples, including compressed sensing and subsurface flow inverse problems.

Keywords:

Mathematics Subject Classification: Primary: 68Q25, 35Q62, 62F15.

Citation:

Full Text(HTML)

Figure 1. Leftmost: Newton iteration. Middle-left: continuum Newton trajectory. Middle-right: ensemble Kalman iteration. Rightmost: continuum ensemble trajectory

Download: Full-size image PowerPoint slide

Figure 2. Parameter estimation and uncertainty quantification in linear example with $ \ell_{0.5} $-regularizations on IEKF and IEKF-SL. Top row: parameter estimation. Bottom row: uncertainty quantification via approximate credible intervals

Download: Full-size image PowerPoint slide

Figure 3. Left: $ \ell_2 $-convergence comparison. Right: regularization effect of $ r $

Download: Full-size image PowerPoint slide

Figure 4. Example in Subsection 4.2. Red: target function to recover. Blue: $ \ell_p $-IEKF recovery. Top row: $ \ell_{1} $-IEKF. Bottom row: $ \ell_{0.5} $-IEKF. Left column: vanilla IEKF. Middle column: $ \ell_p $-IEKF after one outer iteration. Right column: $ \ell_p $-IEKF after three outer iterations. Shaded: 2.5/97.5 percentile of the recovery

Download: Full-size image PowerPoint slide

Figure 5. Example in Subsection 4.2. Red: target function to recover. Blue: $ \ell_p $-IEKF-SL recovery. Top row: $ \ell_{1} $-IEKF-SL. Bottom row: $ \ell_{0.5} $-IEKF-SL. Left column: vanilla IEKF-SL. Middle column: $ \ell_p $-IEKF-SL after one outer iteration. Right column: $ \ell_p $-IEKF-SL after three outer iterations. Shaded: 2.5/97.5 percentile of the recovery

Download: Full-size image PowerPoint slide

Figure 6. Parameter recovery for 2D-elliptic inverse problem based on $ \ell_{1} $/$ \ell_{0.5} $-IEKF. Red: Truth. Blue: $ \ell_p $-IEKF estimate. Left column: vanilla (non-regularized) IEKF. Middle column: $ \ell_p $-IEKF after three outer iterations. Right column: $ \ell_p $-IEKF after six outer iterations. Shaded: elementwise 2.5/97.5 percentile for parameter estimate

Download: Full-size image PowerPoint slide

Figure 7. Parameter recovery for 2D-elliptic inverse problem based on $ \ell_{1} $/$ \ell_{0.5} $-IEKF-SL. Red: Truth. Blue: $ \ell_p $-IEKF-SL estimate. Left column: vanilla (non-regularized) IEKF-SL. Middle column: $ \ell_p $-IEKF-SL after three outer iterations. Right column: $ \ell_p $-IEKF-SL after six outer iterations. Shaded: elementwise 2.5/97.5 percentile for parameter estimate

Download: Full-size image PowerPoint slide

Table 4.1. $ \ell_2 $-error between parameter estimate and true value

	$ \# $ of outer iteration
Method	0th	1st	3rd
$ \ell_{1} $-IEKF $ \ell_{0.5} $-IEKF $ \ell_{1} $-IEKF-SL $ \ell_{0.5} $-IEKF-SL	0.238 0.238 0.205 0.205	0.168 0.148 0.141 0.132	0.094 0.057 0.067 0.037

| Show Table

DownLoad: CSV

Table 4.2. Average width of credible intervals for recovery

	$ \# $ of outer iteration
Method	0th	1st	3rd
$ \ell_{1} $-IEKF $ \ell_{0.5} $-IEKF $ \ell_{1} $-IEKF-SL $ \ell_{0.5} $-IEKF-SL	3.678 3.678 4.660 4.660	5.371 4.945 3.649 3.060	4.228 2.959 2.898 2.400

| Show Table

DownLoad: CSV

Table 4.3. $ \ell_2 $-error between parameter estimate and true value

	$ \# $ of outer iteration
Method	0th	3rd	6th
$ \ell_{1} $-IEKF $ \ell_{0.5} $-IEKF $ \ell_{1} $-IEKF-SL $ \ell_{0.5} $-IEKF-SL	0.030 0.030 0.030 0.030	0.014 0.004 0.020 0.008	0.012 0.002 0.014 0.007

| Show Table

DownLoad: CSV

Table 4.4. Average width of credible intervals for recovery

	$ \# $ of outer iteration
Method	0th	3rd	6th
$ \ell_{1} $-IEKF $ \ell_{0.5} $-IEKF $ \ell_{1} $-IEKF-SL $ \ell_{0.5} $-IEKF-SL	1.211 1.211 1.399 1.399	0.198 0.055 0.259 0.041	0.211 0.017 0.169 0.007

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Agrawal, H. Kim, D. Sanz-Alonso and A. Strang, A variational inference approach to inverse problems with gamma hyperpriors, SIAM/ASA Journal on Uncertainty Quantification, 10 (2022), 1533-1559. doi: 10.1137/21M146209X.
[2]	D. Armbruster, M. Herty and G. Visconti, A stabilization of a continuous limit of the ensemble Kalman inversion, SIAM Journal on Numerical Analysis, 60 (2022), 1494-1515. doi: 10.1137/21M1414000.
[3]	S. Arridge, P. Maass, O. Öktem and C.-B. Schönlieb, Solving inverse problems using data-driven models, Acta Numerica, 28 (2019), 1-174. doi: 10.1017/S0962492919000059.
[4]	J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications, volume 30., Springer Science & Business Media, 2013. doi: 10.1007/978-1-4757-2836-1.
[5]	B. M. Bell and F. W. Cathey, The iterated Kalman filter update as a Gauss-Newton method, IEEE Transactions on Automatic Control, 38 (1993), 294-297. doi: 10.1109/9.250476.
[6]	D. Blömker, 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]	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.
[8]	D. Calvetti, A. Pascarella, F. Pitolli, E. Somersalo and B. Vantaggi, A hierarchical Krylov–Bayes iterative inverse solver for MEG with physiological preconditioning, Inverse Problems, 31 (2015), 125005. doi: 10.1088/0266-5611/31/12/125005.
[9]	D. Calvetti, A. Pascarella, F. Pitolli, E. Somersalo and B. Vantaggi, Brain activity mapping from MEG data via a hierarchical Bayesian algorithm with automatic depth weighting, Brain Topography, 32 (2019), 363-393. doi: 10.1007/s10548-018-0670-7.
[10]	D. Calvetti, F. Pitolli, E. Somersalo and B. Vantaggi, Bayes meets Krylov: Statistically inspired preconditioners for CGLS, SIAM Review, 60 (2018), 429-461. doi: 10.1137/15M1055061.
[11]	D. Calvetti, M. Pragliola and E. Somersalo, Sparsity promoting hybrid solvers for hierarchical Bayesian inverse problems, SIAM Journal on Scientific Computing, 42 (2020), A3761-A3784. doi: 10.1137/20M1326246.
[12]	D. Calvetti, M. Pragliola, E. Somersalo and A. Strang, Sparse reconstructions from few noisy data: Analysis of hierarchical Bayesian models with generalized gamma hyperpriors, Inverse Problems, 36 (2020), 025010. doi: 10.1088/1361-6420/ab4d92.
[13]	D. Calvetti, E. Somersalo and A. Strang, Hierachical Bayesian models and sparsity: $L^2$-magic, Inverse Problems, 35 (2019), 035003. doi: 10.1088/1361-6420/aaf5ab.
[14]	C. M. Carvalho, N. G. Polson and J. G. Scott, Handling sparsity via the horseshoe, In Artificial Intelligence and Statistics, 73-80. PMLR, 2009.
[15]	N. K. Chada, Y. Chen and D. Sanz-Alonso, Iterative ensemble Kalman methods: A unified perspective with some new variants, Foundations of Data Science, 3 (2021), 331-369. doi: 10.3934/fods.2021011.
[16]	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.
[17]	N. K. Chada, A. M. Stuart and X. T. Tong, Tikhonov regularization within ensemble Kalman inversion, SIAM Journal on Numerical Analysis, 58 (2020), 1263-1294. doi: 10.1137/19M1242331.
[18]	N. K. Chada and X. Tong, Convergence acceleration of ensemble Kalman inversion in nonlinear settings, Mathematics of Computation, 91 (2022), 1247-1280. doi: 10.1090/mcom/3709.
[19]	Y. Chen, D. Sanz-Alonso and R. Willett, Autodifferentiable ensemble Kalman filters, SIAM Journal on Mathematics of Data Science, 4 (2022), 801-833. doi: 10.1137/21M1434477.
[20]	P. D. Congdon, Applied Bayesian Hierarchical Methods, Chapman and Hall/CRC, 2010. doi: 10.1201/9781584887218.
[21]	I. Daubechies, R. DeVore, M. Fornasier and C. S. Güntürk, Iteratively reweighted least squares minimization for sparse recovery, Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 63 (2010), 1-38. doi: 10.1002/cpa.20303.
[22]	Z. Ding and Q. Li, Ensemble Kalman sampler: Mean-field limit and convergence analysis, SIAM Journal on Mathematical Analysis, 53 (2021), 1546-1578. doi: 10.1137/20M1339507.
[23]	G. Evans, Sequential data assimilation with a nonlinear quasi-geostrophic model using Monte Carlo methods to forecast error statistics, Journal of Geophysical Research: Oceans, 99 (1995), 10143-10162. doi: 10.1029/94JC00572.
[24]	G. Evans 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.
[25]	G. Evensen, Data Assimilation: The Ensemble Kalman Filter, volume 2., Springer, 2009. doi: 10.1007/978-3-642-03711-5.
[26]	A. Gelman, J. B. Carlin, H. S. Stern and D. B. Rubin, Bayesian Data Analysis, Chapman and Hall/CRC, 1995. doi: 10.1201/9780429258411.
[27]	O. A. Ghattas and D. Sanz-Alonso, Non-Asymptotic analysis of ensemble Kalman updates: Effective dimension and localization, arXiv preprint, arXiv: 2208.03246, 2022.
[28]	I. F. Gorodnitsky and B. D. Rao, Sparse signal reconstruction from limited data using FOCUSS: A re-weighted minimum norm algorithm, IEEE Transactions on Signal Processing, 45 (1997), 600-616. doi: 10.1109/78.558475.
[29]	P. J. Green, Iteratively reweighted least squares for maximum likelihood estimation, and some robust and resistant alternatives, Journal of the Royal Statistical Society: Series B (Methodological), 46 (1984), 149-170. doi: 10.1111/j.2517-6161.1984.tb01288.x.
[30]	C. W. Groetsch, Inverse Problems in the Mathematical Sciences, volume 52., Springer, 1993. doi: 10.1007/978-3-322-99202-4.
[31]	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.
[32]	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.
[33]	M. Herty and G. Visconti, Kinetic methods for inverse problems, Kinetic & Related Models, 12 (2019), 1109-1130. doi: 10.3934/krm.2019042.
[34]	D. Z. Huang, J. Huang, S. Reich and A. M. Stuart, Efficient derivative-free Bayesian inference for large-scale inverse problems, Inverse Problems, 38 (2022), Paper No. 125006, 40 pp, arXiv preprint, arXiv: 2204.04386, 2022. doi: 10.1088/1361-6420/ac99fa.
[35]	M. A. Iglesias, A regularizing iterative ensemble Kalman method for PDE-constrained inverse problems, Inverse Problems, 32 (2016), 025002. doi: 10.1088/0266-5611/32/2/025002.
[36]	M. A. Iglesias, K. J. H. Law and A. M. Stuart, Ensemble Kalman methods for inverse problems, Inverse Problems, 29 (2014), 045001. doi: 10.1088/0266-5611/29/4/045001.
[37]	M. A. Iglesias and Y. Yang, Adaptive regularisation for ensemble Kalman inversion, Inverse Problems, 37 (2021), 025008. doi: 10.1088/1361-6420/abd29b.
[38]	S. I. Kabanikhin, Definitions and examples of inverse and ill-posed problems, J. Inverse Ill-Posed Probl., 16 (2008), 317-357. doi: 10.1515/JIIP.2008.019.
[39]	V. Y. Korolev and A. I. Zeifman, Generalized negative binomial distributions as mixed geometric laws and related limit theorems, Lithuanian Mathematical Journal, 59 (2019), 366-388. doi: 10.1007/s10986-019-09452-x.
[40]	N. B. Kovachki and A. M. Stuart, Ensemble Kalman inversion: A derivative-free technique for machine learning tasks, Inverse Problems, 35 (2019), 095005. doi: 10.1088/1361-6420/ab1c3a.
[41]	K. J. H. Law and V. Zankin, Sparse online variational Bayesian regression, SIAM/ASA Journal on Uncertainty Quantification, 10 (2022), 1070-1100. doi: 10.1137/21M1401188.
[42]	Y. Lee, $\ell_p $ regularization for ensemble Kalman inversion, SIAM Journal on Scientific Computing, 43 (2021), A3417-A3437. doi: 10.1137/20M1365168.
[43]	G. Li and A. C. Reynolds, An iterative ensemble Kalman filter for data assimilation, In SPE Annual Technical Conference and Exhibition, Society of Petroleum Engineers, 2007.
[44]	C. Louizos, M. Welling and D. P. Kingma, Learning sparse neural networks through $ \ell_0$ regularization, arXiv preprint, arXiv: 1712.01312, 2017.
[45]	V. A. Morozov, On the solution of functional equations by the method of regularization, In Doklady Akademii Nauk, volume 167,510-512. Russian Academy of Sciences, 1966.
[46]	B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM Journal on Computing, 24 (1995), 227-234. doi: 10.1137/S0097539792240406.
[47]	J. Pan, Z. Hu, Z. Su and M.-H. Yang, Deblurring text images via $ \ell_0$-regularized intensity and gradient prior, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2014, 2901-2908. doi: 10.1109/CVPR.2014.371.
[48]	J. Pidstrigach and S. Reich, Affine-invariant ensemble transform methods for logistic regression, Foundations of Computational Mathematics, 2022, 1-34. doi: 10.1007/s10208-022-09550-2.
[49]	A. C. Reynolds, M. Zafari and G. Li, Iterative forms of the ensemble Kalman filter, In ECMOR X-10th European Conference on the Mathematics of Oil Recovery, cp-23. European Association of Geoscientists & Engineers, 2006. doi: 10.3997/2214-4609.201402496.
[50]	H. E. Robbins, An empirical Bayes approach to statistics, In Breakthroughs in Statistics, Springer, 1992,388-394. doi: 10.1007/978-1-4612-0919-5_26.
[51]	D. Sanz-Alonso, A. M. Stuart and A. Taeb, Inverse problems and data assimilation, arXiv preprint, arXiv: 1810.06191, 2019.
[52]	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.
[53]	T. Schneider, S. Lan, A. Stuart and J. Teixeira, Earth system modeling 2.0: A blueprint for models that learn from observations and targeted high-resolution simulations, Geophysical Research Letters, 44 (2017), 12-396. doi: 10.1002/2017GL076101.
[54]	T. Schneider, A. M. Stuart and J.-L. Wu, Ensemble kalman inversion for sparse learning of dynamical systems from time-averaged data, Journal of Computational Physics, 470 (2022), 111559. doi: 10.1016/j.jcp.2022.111559.
[55]	A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451-559. doi: 10.1017/S0962492910000061.
[56]	R. Tibshirani, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society: Series B (Methodological), 58 (1996), 267-288. doi: 10.1111/j.2517-6161.1996.tb02080.x.
[57]	P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, 109 (2001), 475-494. doi: 10.1023/A:1017501703105.
[58]	S. Ungarala, On the iterated forms of Kalman filters using statistical linearization, Journal of Process Control, 22 (2012), 935-943. doi: 10.1016/j.jprocont.2012.03.004.
[59]	C. K. Wikle and L. M. Berliner, A Bayesian tutorial for data assimilation, Physica D: Nonlinear Phenomena, 230 (2007), 1-16. doi: 10.1016/j.physd.2006.09.017.
[60]	H. Zou, The adaptive lasso and its oracle properties, Journal of the American Statistical Association, 101 (2006), 1418-1429. doi: 10.1198/016214506000000735.