Efficient solution of boundary-value problems for image reconstruction viasampling

Noninvasive imaging based on wave scattering remains a difficult problem in those cases where the forward map can only be adequately simulated by solv ing the appropriate partial-differential equation subject to boundary condi tions. We develop a method for solving these linear boundary-value problems which is efficient and exact, trading off storage requirements against com putation time. The method is based on using the present solution within the Woodbury formula for updating solutions given changes in the trial image, or state. Hence the method merges well with the Metropolis-Hastings algorit hm using localized updates. The scaling of the method as a function of imag e size and measurement set size is given. We conclude that this method is c onsiderably more efficient than earlier algorithms that we have used to dem onstrate sampling for inverse problems in this class. We give examples of s ampling for imaging electrical conductivity from a simple synthetic data se t. Full Bayesian inference is demonstrated with expectations calculated ove r the posterior for Potts-type prior distributions. (C) 2000 SPIE and IS&T. [S1017-9909(00)00302-0].