• Previous Article
    High-order total variation regularization approach for axially symmetric object tomography from a single radiograph
  • IPI Home
  • This Issue
  • Next Article
    Optimization approach for the simultaneous reconstruction of the dielectric permittivity and magnetic permeability functions from limited observations
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 and 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-137. 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-171. 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-23 (electronic). doi: 10.1137/S1064827595289108.

[4]

T. Bui-Thanh, Model-Constrained Optimization Methods for Reduction of Parameterized Large-Scale Systems, PhD thesis, Department of Aeronautics and Astronautics, MIT, 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), 055001, 32pp. 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), p. 055002.

[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-3288. 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-445. doi: 10.1137/0806023.

[11]

S. Comelli, A Novel Class of Priors for Edge-Preserving Methods in Bayesian Inversion, master's thesis, Universita Degli Studi Di Milano, 2011.

[12]

M. Dashti, S. Harris and A. Stuart, Besov priors for Bayesian inverse problems, Inverse Problems and Imaging, 6 (2012), 183-200. doi: 10.3934/ipi.2012.6.183.

[13]

I. Daubechies, Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, 61. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 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-1457. 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, Festschrift for Klaus Ritter, H. Fischer, B. Riedmüller, and S. Schäffler, eds., Heidelberg, (1996), Physica-Verlag, pp. 97-107.

[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-597. 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-716. 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-343. doi: 10.1137/080725891.

[19]

A. Grasmair, M. Haltmeier and O. Scherzer, Sparse regularization with $l^q$ penalty term, Inverse Problems, 24 (2008), 055020, 13pp. 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), B644-B665. 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-635. 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-197. doi: 10.1007/s10589-006-6514-5.

[23]

C. T. Kelley, Iterative Methods for Optimization, SIAM, Philadelphia, 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-617.

[25]

V. Kolehmainen, M. Lassas, K. Niinimaki and S. Siltanen, Sparsity-promoting Bayesian inversion, Inverse Problems, 28 (2012), 025005, 28pp. 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), 64 pp.

[27]

M. Lassas, E. Saksman and S. Siltanen, Discretization invariant Bayesian inversion and Besov space priors, Inverse Problems and Imaging, 3 (2009), 87-122. 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-612. 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-1127. doi: 10.1137/S1052623498345075.

[30]

D. A. Lorenz and D. Trede, Optimal convergence rates for Tikhonov regularization in Besov scales, Inverse Problems, 24 (2008), 055010, 14pp. 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-1195. 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-601. doi: 10.1137/0802028.

[33]

P. Piiroinen, Statistical Measurements, Experiments, and Applications, PhD thesis, Department of Mathematics and Statistics, University of Helsinki, 2005.

[34]

D. F. Shanno and R. J. Vanderbei, An interior-point method for nonconvex nonlinear programming, Computational Optimization and Applications, 13 (1999), 231-252. doi: 10.1023/A:1008677427361.

[35]

A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451-559. doi: 10.1017/S0962492910000061.

[36]

H. Triebel, Theory of Function Spaces III, vol. 100, Birhäuser Verlag, 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-180. 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-54. doi: 10.1007/978-3-642-30367-8_2.

[39]

S. J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, PA, 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-560. 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-137. 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-171. 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-23 (electronic). doi: 10.1137/S1064827595289108.

[4]

T. Bui-Thanh, Model-Constrained Optimization Methods for Reduction of Parameterized Large-Scale Systems, PhD thesis, Department of Aeronautics and Astronautics, MIT, 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), 055001, 32pp. 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), p. 055002.

[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-3288. 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-445. doi: 10.1137/0806023.

[11]

S. Comelli, A Novel Class of Priors for Edge-Preserving Methods in Bayesian Inversion, master's thesis, Universita Degli Studi Di Milano, 2011.

[12]

M. Dashti, S. Harris and A. Stuart, Besov priors for Bayesian inverse problems, Inverse Problems and Imaging, 6 (2012), 183-200. doi: 10.3934/ipi.2012.6.183.

[13]

I. Daubechies, Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, 61. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 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-1457. 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, Festschrift for Klaus Ritter, H. Fischer, B. Riedmüller, and S. Schäffler, eds., Heidelberg, (1996), Physica-Verlag, pp. 97-107.

[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-597. 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-716. 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-343. doi: 10.1137/080725891.

[19]

A. Grasmair, M. Haltmeier and O. Scherzer, Sparse regularization with $l^q$ penalty term, Inverse Problems, 24 (2008), 055020, 13pp. 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), B644-B665. 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-635. 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-197. doi: 10.1007/s10589-006-6514-5.

[23]

C. T. Kelley, Iterative Methods for Optimization, SIAM, Philadelphia, 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-617.

[25]

V. Kolehmainen, M. Lassas, K. Niinimaki and S. Siltanen, Sparsity-promoting Bayesian inversion, Inverse Problems, 28 (2012), 025005, 28pp. 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), 64 pp.

[27]

M. Lassas, E. Saksman and S. Siltanen, Discretization invariant Bayesian inversion and Besov space priors, Inverse Problems and Imaging, 3 (2009), 87-122. 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-612. 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-1127. doi: 10.1137/S1052623498345075.

[30]

D. A. Lorenz and D. Trede, Optimal convergence rates for Tikhonov regularization in Besov scales, Inverse Problems, 24 (2008), 055010, 14pp. 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-1195. 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-601. doi: 10.1137/0802028.

[33]

P. Piiroinen, Statistical Measurements, Experiments, and Applications, PhD thesis, Department of Mathematics and Statistics, University of Helsinki, 2005.

[34]

D. F. Shanno and R. J. Vanderbei, An interior-point method for nonconvex nonlinear programming, Computational Optimization and Applications, 13 (1999), 231-252. doi: 10.1023/A:1008677427361.

[35]

A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451-559. doi: 10.1017/S0962492910000061.

[36]

H. Triebel, Theory of Function Spaces III, vol. 100, Birhäuser Verlag, 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-180. 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-54. doi: 10.1007/978-3-642-30367-8_2.

[39]

S. J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, PA, 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-560. doi: 10.1145/279232.279236.

[1]

Matti Lassas, Eero Saksman, Samuli Siltanen. Discretization-invariant Bayesian inversion and Besov space priors. Inverse Problems and 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 and 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 and Imaging, 2016, 10 (4) : 943-975. doi: 10.3934/ipi.2016028

[4]

Chen Li, Matthew Dunlop, Georg Stadler. Bayesian neural network priors for edge-preserving inversion. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022022

[5]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237

[6]

Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial and Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775

[7]

Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919

[8]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309

[9]

Masoumeh Dashti, Stephen Harris, Andrew Stuart. Besov priors for Bayesian inverse problems. Inverse Problems and Imaging, 2012, 6 (2) : 183-200. doi: 10.3934/ipi.2012.6.183

[10]

Yunwen Yin, Weishi Yin, Pinchao Meng, Hongyu Liu. The interior inverse scattering problem for a two-layered cavity using the Bayesian method. Inverse Problems and Imaging, 2022, 16 (4) : 673-690. doi: 10.3934/ipi.2021069

[11]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104

[12]

Jirui Ma, Jinyan Fan. On convergence properties of the modified trust region method under Hölderian error bound condition. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021222

[13]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[14]

Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial and Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143

[15]

Fang Zeng, Pablo Suarez, Jiguang Sun. A decomposition method for an interior inverse scattering problem. Inverse Problems and Imaging, 2013, 7 (1) : 291-303. doi: 10.3934/ipi.2013.7.291

[16]

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 and Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169

[17]

Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235

[18]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011

[19]

Jiangfeng Huang, Zhiliang Deng, Liwei Xu. A Bayesian level set method for an inverse medium scattering problem in acoustics. Inverse Problems and Imaging, 2021, 15 (5) : 1077-1097. doi: 10.3934/ipi.2021029

[20]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283

2020 Impact Factor: 1.639

Metrics

  • PDF downloads (137)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]