Browsing by Author "Kilmer, Misha E."
Now showing 1 - 6 of 6
Results Per Page
Sort Options
- Computing Reduced Order Models via Inner-Outer Krylov Recycling in Diffuse Optical TomographyO'Connell, Meghan; Kilmer, Misha E.; de Sturler, Eric; Gugercin, Serkan (Siam Publications, 2017-01-01)In nonlinear imaging problems whose forward model is described by a partial differential equation (PDE), the main computational bottleneck in solving the inverse problem is the need to solve many large-scale discretized PDEs at each step of the optimization process. In the context of absorption imaging in diffuse optical tomography, one approach to addressing this bottleneck proposed recently (de Sturler, et al, 2015) reformulates the viewing of the forward problem as a differential algebraic system, and then employs model order reduction (MOR). However, the construction of the reduced model requires the solution of several full order problems (i.e. the full discretized PDE for multiple right-hand sides) to generate a candidate global basis. This step is then followed by a rank-revealing factorization of the matrix containing the candidate basis in order to compress the basis to a size suitable for constructing the reduced transfer function. The present paper addresses the costs associated with the global basis approximation in two ways. First, we use the structure of the matrix to rewrite the full order transfer function, and corresponding derivatives, such that the full order systems to be solved are symmetric (positive definite in the zero frequency case). Then we apply MOR to the new formulation of the problem. Second, we give an approach to computing the global basis approximation dynamically as the full order systems are solved. In this phase, only the incrementally new, relevant information is added to the existing global basis, and redundant information is not computed. This new approach is achieved by an inner-outer Krylov recycling approach which has potential use in other applications as well. We show the value of the new approach to approximate global basis computation on two DOT absorption image reconstruction problems.
- Nonlinear Parametric Inversion Using Interpolatory Model Reductionde Sturler, Eric; Gugercin, Serkan; Kilmer, Misha E.; Chaturantabut, Saifon; Beattie, Christopher A.; O'Connell, Meghan (Siam Publications, 2015-01-01)Nonlinear parametric inverse problems appear in several prominent applications; one such application is Diffuse Optical Tomography (DOT) in medical image reconstruction. Such inverse problems present huge computational challenges, mostly due to the need for solving a sequence of large-scale discretized, parametrized, partial diferential equations (PDEs) in the forward model. In this paper, we show how interpolatory parametric model reduction can significantly reduce the cost of the inversion process in DOT by drastically reducing the computational cost of solving the forward problems. The key observation is that function evaluations for the underlying optimization problem may be viewed as transfer function evaluations along the imaginary axis; a similar observation holds for Jacobian evaluations as well. This motivates the use of system-theoretic model order reduction methods. We discuss the construction and use of interpolatory parametric reduced models as surrogates for the full forward model. Within the DOT setting, these surrogate models can approximate both the cost functional and the associated Jacobian with very little loss of accuracy while significantly reducing the cost of the overall inversion process. Four numerical examples illustrate the effciency of the proposed approach. Although we focus on DOT in this paper, we believe that our approach is applicable much more generally.
- Randomization for Efficient Nonlinear Parametric InversionSariaydin, Selin (Virginia Tech, 2018-06-04)Nonlinear parametric inverse problems appear in many applications in science and engineering. We focus on diffuse optical tomography (DOT) in medical imaging. DOT aims to recover an unknown image of interest, such as the absorption coefficient in tissue to locate tumors in the body. Using a mathematical (forward) model to predict measurements given a parametrization of the tissue, we minimize the misfit between predicted and actual measurements up to a given noise level. The main computational bottleneck in such inverse problems is the repeated evaluation of this large-scale forward model, which corresponds to solving large linear systems for each source and frequency at each optimization step. Moreover, to efficiently compute derivative information, we need to solve, repeatedly, linear systems with the adjoint for each detector and frequency. As rapid advances in technology allow for large numbers of sources and detectors, these problems become computationally prohibitive. In this thesis, we introduce two methods to drastically reduce this cost. To efficiently implement Newton methods, we extend the use of simultaneous random sources to reduce the number of linear system solves to include simultaneous random detectors. Moreover, we combine simultaneous random sources and detectors with optimized ones that lead to faster convergence and more accurate solutions. We can use reduced order models (ROM) to drastically reduce the size of the linear systems to be solved in each optimization step while still solving the inverse problem accurately. However, the construction of the ROM bases still incurs a substantial cost. We propose to use randomization to drastically reduce the number of large linear solves needed for constructing the global ROM bases without degrading the accuracy of the solution to the inversion problem. We demonstrate the efficiency of these approaches with 2-dimensional and 3-dimensional examples from DOT; however, our methods have the potential to be useful for other applications as well.
- Randomized Approach to Nonlinear Inversion Combining Simultaneous Random and Optimized Sources and DetectorsSariaydin Aslan, S.; de Sturler, Eric; Kilmer, Misha E. (Society For Industrial And Applied Mathematics, 2017-07-26)In partial differential equations-based inverse problems with many measurements, we have to solve many large linear system for each evaluation of the objective function. In the nonlinear case, each evaluation of the Jacobian requires solving an additional set of systems. This leads to a tremendous computational cost, which is by far the dominant cost for these problems. Several authors have proposed to drastically reduce the number of system solves by exploiting stochastic techniques [Haber et al., SIAM Optim., 22:739-757] and posing the problem as a stochastic optimization problem [Shapiro et al., Lectures on Stochastic Programming, SIAM, 2009]. In this approach, the objective function is estimated using only a few random linear combinations of the sources, referred to as simultaneous random sources. For the Jacobian, we show that a similar approach can be used to reduce the number of additional adjoint solves for the detectors. While others have reported good solution quality at a greatly reduced computational cost using these randomized approaches, for our problem of interest, diffuse optical tomography, the approach often does not lead to sufficiently accurate solutions. Therefore, we replace a few random simultaneous sources and detectors by simultaneous sources and detectors that are optimized to maximize the Frobenius norm of the sampled Jacobian after solving to a modest tolerance. This choice is inspired by (1) the regularized model problem solves in the TREGS nonlinear least squares solver [de Sturler and Kilmer, SIAM Sci. Comput., 33:3057-3086] used for minimization in our method and (2) the fact that these optimized directions correspond to the most informative data components. Our approach leads to solutions of the same quality as obtained using all sources and detectors but at a greatly reduced computational cost.
- Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problemsSaibaba, Arvind K.; Prasad, Pranjal; de Sturler, Eric; Miller, Eric; Kilmer, Misha E. (Academic Press – Elsevier, 2021-09-01)Markov chain Monte Carlo (MCMC) approaches are traditionally used for uncertainty quantification in inverse problems where the physics of the underlying sensor modality is described by a partial differential equation (PDE). However, the use of MCMC algorithms is prohibitively expensive in applications where each log-likelihood evaluation may require hundreds to thousands of PDE solves corresponding to multiple sensors; i.e., spatially distributed sources and receivers perhaps operating at different frequencies or wavelengths depending on the precise application. We show how to mitigate the computational cost of each log-likelihood evaluation by using several randomized techniques and embed these randomized approximations within MCMC algorithms. The resulting MCMC algorithms are computationally efficient methods for quantifying the uncertainty associated with the reconstructed parameters. We demonstrate the accuracy and computational benefits of our proposed algorithms on a model application from diffuse optical tomography where we invert for the spatial distribution of optical absorption.
- A regularized Gauss-Newton trust region approach to imaging in diffuse optical tomographyde Sturler, Eric; Kilmer, Misha E. (Siam Publications, 2011)We present a new algorithm for the solution of nonlinear least squares problems arising from parameterized imaging problems with diffuse optical tomographic data [D. Boas et al., IEEE Signal Process. Mag., 18 (2001), pp. 57-75]. The parameterization arises from the use of parametric level sets for regularization [M.E. Kilmer et al., Proc. SPIE, 5559 (2004), pp. 381-391], [A. Aghasi, M.E. Kilmer, and E.L. Miller, SIAM J. Imaging Sci., 4 (2011), pp. 618-650]. Such problems lead to Jacobians that have relatively few columns, a relatively modest number of rows, and are ill-conditioned. Moreover, such problems have function and Jacobian evaluations that are computationally expensive. Our optimization algorithm is appropriate for any inverse or imaging problem with those characteristics. In fact, we expect our algorithm to be effective for more general problems with ill-conditioned Jacobians. The algorithm aims to minimize the total number of function and Jacobian evaluations by analyzing which spectral components of the Gauss-Newton direction should be discarded or damped. The analysis considers for each component the reduction of the objective function and the contribution to the search direction, restricting the computed search direction to be within a trust region. The result is a truncated SVD-like approach to choosing the search direction. However, we do not necessarily discard components in order of decreasing singular value, and some components may be scaled to maintain fidelity to the trust region model. Our algorithm uses the Basic Trust Region Algorithm from [A.R. Conn, N.I.M. Gould, and Ph. L. Toint, Trust-Region Methods, SIAM, Philadelphia, 2000]. We prove that our algorithm is globally convergent to a critical point. Our numerical results show that the new algorithm generally outperforms competing methods applied to the DOT imaging problem with parametric level sets, and regularly does so by a significant factor.