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

Tan Bui-Thanh; Omar Ghattas

doi:10.3934/ipi.2015.9.27

Article Contents

2015, Volume 9, Issue 1: 27-53. Doi: 10.3934/ipi.2015.9.27

This issue Previous Article Optimization approach for the simultaneous reconstruction of the dielectric permittivity and magnetic permeability functions from limited observations Next Article High-order total variation regularization approach for axially symmetric object tomography from a single radiograph

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

Tan Bui-Thanh^1, and
Omar Ghattas^2,

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: October 31, 2012

Revised: August 31, 2013

Published: January 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 62G99, 49N45; Secondary: 49K20, 49K21.

Citation:

Related Papers

Cited by

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.