# American Institute of Mathematical Sciences

• Previous Article
Optimization approach for the simultaneous reconstruction of the dielectric permittivity and magnetic permeability functions from limited observations
• IPI Home
• This Issue
• Next Article
High-order total variation regularization approach for axially symmetric object tomography from a single radiograph
February  2015, 9(1): 27-53. doi: 10.3934/ipi.2015.9.27

## A scalable algorithm for MAP estimators in Bayesian inverse problems with Besov priors

 1 Department of Aerospace Engineering and Engineering Mechanics, Institute for Computational Engineering & Sciences, The University of Texas at Austin, Austin, TX 78712 2 Institute for Computational Engineering & Sciences, Jackson School of Geosciences, and Department of Mechanical Engineering, The University of Texas at Austin, Austin, TX 78712

Received  November 2012 Revised  September 2013 Published  January 2015

We present a scalable solver for approximating the maximum a posteriori (MAP) point of Bayesian inverse problems with Besov priors based on wavelet expansions with random coefficients. It is a subspace trust region interior reflective Newton conjugate gradient method for bound constrained optimization problems. The method combines the rapid locally-quadratic convergence rate properties of Newton's method, the effectiveness of trust region globalization for treating ill-conditioned problems, and the Eisenstat--Walker idea of preventing oversolving. We demonstrate the scalability of the proposed method on two inverse problems: a deconvolution problem and a coefficient inverse problem governed by elliptic partial differential equations. The numerical results show that the number of Newton iterations is independent of the number of wavelet coefficients $n$ and the computation time scales linearly in $n$. It will be numerically shown, under our implementations, that the proposed solver is two times faster than the split Bregman approach, and it is an order of magnitude less expensive than the interior path following primal-dual method. Our results also confirm the fact that the Besov $\mathbb{B}_{11}^1$ prior is sparsity promoting, discretization-invariant, and edge-preserving for both imaging and inverse problems governed by partial differential equations.
Citation: Tan Bui-Thanh, Omar Ghattas. A scalable algorithm for MAP estimators in Bayesian inverse problems with Besov priors. Inverse Problems & Imaging, 2015, 9 (1) : 27-53. doi: 10.3934/ipi.2015.9.27
##### References:
 [1] M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems,, Acta Numerica, 14 (2005), 1. doi: 10.1017/S0962492904000212. [2] L. Bergamaschi, J. Gondzio and G. Zilli, Preconditioning indefinite systems in interior point methods for optimization,, Computational Optimization and Applications, 28 (2004), 149. doi: 10.1023/B:COAP.0000026882.34332.1b. [3] M. A. Branch, T. F. Coleman and Y. Li, A subspace, interior, and conjugate gradient method for large-scale bound-constrained minimization problems,, SIAM Journal on Scientific Computing, 21 (1999), 1. doi: 10.1137/S1064827595289108. [4] T. Bui-Thanh, Model-Constrained Optimization Methods for Reduction of Parameterized Large-Scale Systems,, PhD thesis, (2007). [5] T. Bui-Thanh and O. Ghattas, Analysis of the Hessian for inverse scattering problems. Part I: Inverse shape scattering of acoustic waves,, Inverse Problems, 28 (2012). doi: 10.1088/0266-5611/28/5/055001. [6] ________, Analysis of the Hessian for inverse scattering problems. Part II: Inverse medium scattering of acoustic waves,, Inverse Problems, 28 (2012). [7] ________, Analysis of the Hessian for inverse scattering problems. Part III: Inverse medium scattering of electromagnetic waves., Submitted to Inverse Problems, (2012). [8] ________, A scaled stochastic Newton algorithm for Markov chain Monte Carlo simulations,, Submitted to SIAM Journal of Uncertainty Quantification, (2012). [9] T. Bui-Thanh, K. Willcox and O. Ghattas, Model reduction for large-scale systems with high-dimensional parametric input space,, SIAM Journal on Scientific Computing, 30 (2008), 3270. doi: 10.1137/070694855. [10] T. F. Coleman and Y. Li, An interior trust region approach for nonlinear minimization subject to bounds,, SIAM Journal on Optimization, 6 (1996), 418. doi: 10.1137/0806023. [11] S. Comelli, A Novel Class of Priors for Edge-Preserving Methods in Bayesian Inversion,, master's thesis, (2011). [12] M. Dashti, S. Harris and A. Stuart, Besov priors for Bayesian inverse problems,, Inverse Problems and Imaging, 6 (2012), 183. doi: 10.3934/ipi.2012.6.183. [13] I. Daubechies, Ten Lectures on Wavelets,, CBMS-NSF Regional Conference Series in Applied Mathematics, (1992). doi: 10.1137/1.9781611970104. [14] I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,, Communications on Pure and Applied Mathematics, 57 (2004), 1413. doi: 10.1002/cpa.20042. [15] J. E. Dennis and L. N. Vicente, Trust-region interior-point algorithms for minimization methods with simple bounds,, in Applied Mathematics and Parallel Computing, (1996), 97. [16] M. A. T. Figueiredo, R. D. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems,, IEEE Journal of Selected Topics in Signal Processing, 1 (2007), 586. doi: 10.1109/JSTSP.2007.910281. [17] J. N. Franklin, Well-posed stochastic extensions of ill-posed linear problems,, Journal of Mathematical Analysis and Applications, 31 (1970), 682. doi: 10.1016/0022-247X(70)90017-X. [18] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems,, SIAM Journal on Imaging Sciences, 2 (2009), 323. doi: 10.1137/080725891. [19] A. Grasmair, M. Haltmeier and O. Scherzer, Sparse regularization with $l^q$ penalty term,, Inverse Problems, 24 (2008). doi: 10.1088/0266-5611/24/5/055020. [20] K. Hamalainen, A. Kallonen, V. Kolehmainen, M. Lassas, K. Niinimaki and S. Siltanen, Sparse tomography,, SIAM J. Sci. Comput., 35 (2013). doi: 10.1137/120876277. [21] M. Heinkenschloss, M. Ulbrich and S. Ulbrich, Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption,, Mathematical Programming, 86 (1999), 615. doi: 10.1007/s101070050107. [22] C. Kanzow and A. Klug, On affine-scaling interior-point Newton methods for nonlinear minimization with bound constraints,, Computational Optimization and Applications, 35 (2006), 177. doi: 10.1007/s10589-006-6514-5. [23] C. T. Kelley, Iterative Methods for Optimization,, SIAM, (1999). doi: 10.1137/1.9781611970920. [24] S.-J. Kim, K. Koh, M. Lustig, S. Boyd and D. Gorinevsky, An interior-point method for large-scale $l_1$-regularized least squares,, IEEE Journal of Selected Topics in Signal Processing, 1 (2007), 606. [25] V. Kolehmainen, M. Lassas, K. Niinimaki and S. Siltanen, Sparsity-promoting Bayesian inversion,, Inverse Problems, 28 (2012). doi: 10.1088/0266-5611/28/2/025005. [26] S. Lasanen, Discretizations of generalized random variables with applications to inverse problems,, Ann. Acad. Sci. Fenn. Math. Diss., 2002 (2002). [27] M. Lassas, E. Saksman and S. Siltanen, Discretization invariant Bayesian inversion and Besov space priors,, Inverse Problems and Imaging, 3 (2009), 87. doi: 10.3934/ipi.2009.3.87. [28] M. S. Lehtinen, L. Päivärinta and E. Somersalo, Linear inverse problems for generalized random variables,, Inverse Problems, 5 (1989), 599. doi: 10.1088/0266-5611/5/4/011. [29] C.-J. Lin and J. J. Moré, Newton's method for large bound-constrained optimization problems,, SIAM Journal on Optimization, 9 (1999), 1100. doi: 10.1137/S1052623498345075. [30] D. A. Lorenz and D. Trede, Optimal convergence rates for Tikhonov regularization in Besov scales,, Inverse Problems, 24 (2008). doi: 10.1088/0266-5611/24/5/055010. [31] M. Lustig, D. Donoho and J. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging,, Journal of Magnetic Resonance Imaging, 58 (2007), 1182. doi: 10.1002/mrm.21391. [32] S. Mehrotra, On the implementation of a primal-dual interior point method,, SIAM Journal on Optimization, 2 (1992), 575. doi: 10.1137/0802028. [33] P. Piiroinen, Statistical Measurements, Experiments, and Applications,, PhD thesis, (2005). [34] D. F. Shanno and R. J. Vanderbei, An interior-point method for nonconvex nonlinear programming,, Computational Optimization and Applications, 13 (1999), 231. doi: 10.1023/A:1008677427361. [35] A. M. Stuart, Inverse problems: A Bayesian perspective,, Acta Numerica, 19 (2010), 451. doi: 10.1017/S0962492910000061. [36] H. Triebel, Theory of Function Spaces III,, vol. 100, (2006). [37] J. Trzasko, A. Manduca and E. Borisch, Sparse MRI reconstruction via multiscale L0-continuation,, in Proceedings of the 14th IEEE/SP Workshop o Satistical Signal Processing, (2007), 176. doi: 10.1109/SSP.2007.4301242. [38] B. Vexler, Adaptive finite element methods for parameter identification problems,, Contributions in Mathematical and Computational Sciences, 4 (2013), 31. doi: 10.1007/978-3-642-30367-8_2. [39] S. J. Wright, Primal-Dual Interior-Point Methods,, SIAM, (1997). doi: 10.1137/1.9781611971453. [40] C. Zhu, R. H. Byrd, P. Lu and J. Nocedal, L-bfgs-b - fortran subroutines for large-scale bound constrained optimization,, ACM Transactions on Mathematical Software, 23 (1997), 550. doi: 10.1145/279232.279236.

show all references

##### References:
 [1] M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems,, Acta Numerica, 14 (2005), 1. doi: 10.1017/S0962492904000212. [2] L. Bergamaschi, J. Gondzio and G. Zilli, Preconditioning indefinite systems in interior point methods for optimization,, Computational Optimization and Applications, 28 (2004), 149. doi: 10.1023/B:COAP.0000026882.34332.1b. [3] M. A. Branch, T. F. Coleman and Y. Li, A subspace, interior, and conjugate gradient method for large-scale bound-constrained minimization problems,, SIAM Journal on Scientific Computing, 21 (1999), 1. doi: 10.1137/S1064827595289108. [4] T. Bui-Thanh, Model-Constrained Optimization Methods for Reduction of Parameterized Large-Scale Systems,, PhD thesis, (2007). [5] T. Bui-Thanh and O. Ghattas, Analysis of the Hessian for inverse scattering problems. Part I: Inverse shape scattering of acoustic waves,, Inverse Problems, 28 (2012). doi: 10.1088/0266-5611/28/5/055001. [6] ________, Analysis of the Hessian for inverse scattering problems. Part II: Inverse medium scattering of acoustic waves,, Inverse Problems, 28 (2012). [7] ________, Analysis of the Hessian for inverse scattering problems. Part III: Inverse medium scattering of electromagnetic waves., Submitted to Inverse Problems, (2012). [8] ________, A scaled stochastic Newton algorithm for Markov chain Monte Carlo simulations,, Submitted to SIAM Journal of Uncertainty Quantification, (2012). [9] T. Bui-Thanh, K. Willcox and O. Ghattas, Model reduction for large-scale systems with high-dimensional parametric input space,, SIAM Journal on Scientific Computing, 30 (2008), 3270. doi: 10.1137/070694855. [10] T. F. Coleman and Y. Li, An interior trust region approach for nonlinear minimization subject to bounds,, SIAM Journal on Optimization, 6 (1996), 418. doi: 10.1137/0806023. [11] S. Comelli, A Novel Class of Priors for Edge-Preserving Methods in Bayesian Inversion,, master's thesis, (2011). [12] M. Dashti, S. Harris and A. Stuart, Besov priors for Bayesian inverse problems,, Inverse Problems and Imaging, 6 (2012), 183. doi: 10.3934/ipi.2012.6.183. [13] I. Daubechies, Ten Lectures on Wavelets,, CBMS-NSF Regional Conference Series in Applied Mathematics, (1992). doi: 10.1137/1.9781611970104. [14] I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,, Communications on Pure and Applied Mathematics, 57 (2004), 1413. doi: 10.1002/cpa.20042. [15] J. E. Dennis and L. N. Vicente, Trust-region interior-point algorithms for minimization methods with simple bounds,, in Applied Mathematics and Parallel Computing, (1996), 97. [16] M. A. T. Figueiredo, R. D. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems,, IEEE Journal of Selected Topics in Signal Processing, 1 (2007), 586. doi: 10.1109/JSTSP.2007.910281. [17] J. N. Franklin, Well-posed stochastic extensions of ill-posed linear problems,, Journal of Mathematical Analysis and Applications, 31 (1970), 682. doi: 10.1016/0022-247X(70)90017-X. [18] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems,, SIAM Journal on Imaging Sciences, 2 (2009), 323. doi: 10.1137/080725891. [19] A. Grasmair, M. Haltmeier and O. Scherzer, Sparse regularization with $l^q$ penalty term,, Inverse Problems, 24 (2008). doi: 10.1088/0266-5611/24/5/055020. [20] K. Hamalainen, A. Kallonen, V. Kolehmainen, M. Lassas, K. Niinimaki and S. Siltanen, Sparse tomography,, SIAM J. Sci. Comput., 35 (2013). doi: 10.1137/120876277. [21] M. Heinkenschloss, M. Ulbrich and S. Ulbrich, Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption,, Mathematical Programming, 86 (1999), 615. doi: 10.1007/s101070050107. [22] C. Kanzow and A. Klug, On affine-scaling interior-point Newton methods for nonlinear minimization with bound constraints,, Computational Optimization and Applications, 35 (2006), 177. doi: 10.1007/s10589-006-6514-5. [23] C. T. Kelley, Iterative Methods for Optimization,, SIAM, (1999). doi: 10.1137/1.9781611970920. [24] S.-J. Kim, K. Koh, M. Lustig, S. Boyd and D. Gorinevsky, An interior-point method for large-scale $l_1$-regularized least squares,, IEEE Journal of Selected Topics in Signal Processing, 1 (2007), 606. [25] V. Kolehmainen, M. Lassas, K. Niinimaki and S. Siltanen, Sparsity-promoting Bayesian inversion,, Inverse Problems, 28 (2012). doi: 10.1088/0266-5611/28/2/025005. [26] S. Lasanen, Discretizations of generalized random variables with applications to inverse problems,, Ann. Acad. Sci. Fenn. Math. Diss., 2002 (2002). [27] M. Lassas, E. Saksman and S. Siltanen, Discretization invariant Bayesian inversion and Besov space priors,, Inverse Problems and Imaging, 3 (2009), 87. doi: 10.3934/ipi.2009.3.87. [28] M. S. Lehtinen, L. Päivärinta and E. Somersalo, Linear inverse problems for generalized random variables,, Inverse Problems, 5 (1989), 599. doi: 10.1088/0266-5611/5/4/011. [29] C.-J. Lin and J. J. Moré, Newton's method for large bound-constrained optimization problems,, SIAM Journal on Optimization, 9 (1999), 1100. doi: 10.1137/S1052623498345075. [30] D. A. Lorenz and D. Trede, Optimal convergence rates for Tikhonov regularization in Besov scales,, Inverse Problems, 24 (2008). doi: 10.1088/0266-5611/24/5/055010. [31] M. Lustig, D. Donoho and J. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging,, Journal of Magnetic Resonance Imaging, 58 (2007), 1182. doi: 10.1002/mrm.21391. [32] S. Mehrotra, On the implementation of a primal-dual interior point method,, SIAM Journal on Optimization, 2 (1992), 575. doi: 10.1137/0802028. [33] P. Piiroinen, Statistical Measurements, Experiments, and Applications,, PhD thesis, (2005). [34] D. F. Shanno and R. J. Vanderbei, An interior-point method for nonconvex nonlinear programming,, Computational Optimization and Applications, 13 (1999), 231. doi: 10.1023/A:1008677427361. [35] A. M. Stuart, Inverse problems: A Bayesian perspective,, Acta Numerica, 19 (2010), 451. doi: 10.1017/S0962492910000061. [36] H. Triebel, Theory of Function Spaces III,, vol. 100, (2006). [37] J. Trzasko, A. Manduca and E. Borisch, Sparse MRI reconstruction via multiscale L0-continuation,, in Proceedings of the 14th IEEE/SP Workshop o Satistical Signal Processing, (2007), 176. doi: 10.1109/SSP.2007.4301242. [38] B. Vexler, Adaptive finite element methods for parameter identification problems,, Contributions in Mathematical and Computational Sciences, 4 (2013), 31. doi: 10.1007/978-3-642-30367-8_2. [39] S. J. Wright, Primal-Dual Interior-Point Methods,, SIAM, (1997). doi: 10.1137/1.9781611971453. [40] C. Zhu, R. H. Byrd, P. Lu and J. Nocedal, L-bfgs-b - fortran subroutines for large-scale bound constrained optimization,, ACM Transactions on Mathematical Software, 23 (1997), 550. doi: 10.1145/279232.279236.
 [1] Matti Lassas, Eero Saksman, Samuli Siltanen. Discretization-invariant Bayesian inversion and Besov space priors. Inverse Problems & Imaging, 2009, 3 (1) : 87-122. doi: 10.3934/ipi.2009.3.87 [2] Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171 [3] Tan Bui-Thanh, Quoc P. Nguyen. FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems. Inverse Problems & Imaging, 2016, 10 (4) : 943-975. doi: 10.3934/ipi.2016028 [4] Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237 [5] Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775 [6] Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919 [7] Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309 [8] Masoumeh Dashti, Stephen Harris, Andrew Stuart. Besov priors for Bayesian inverse problems. Inverse Problems & Imaging, 2012, 6 (2) : 183-200. doi: 10.3934/ipi.2012.6.183 [9] Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949 [10] Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143 [11] Fang Zeng, Pablo Suarez, Jiguang Sun. A decomposition method for an interior inverse scattering problem. Inverse Problems & Imaging, 2013, 7 (1) : 291-303. doi: 10.3934/ipi.2013.7.291 [12] Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235 [13] Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169 [14] Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011 [15] Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283 [16] Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 [17] Biao Qu, Naihua Xiu. A relaxed extragradient-like method for a class of constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 645-654. doi: 10.3934/jimo.2007.3.645 [18] Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 [19] Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391 [20] Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041

2018 Impact Factor: 1.469