Randomized Approach to Nonlinear Inversion Combining Simultaneous Random and Optimized Sources and Detectors

In partial differential equations-based (PDE-based) inverse problems with many measurements, many large-scale discretized PDEs must be solved for each evaluation of the misfit or objective function. In the nonlinear case, evaluating the Jacobian requires solving an additional set of systems. This leads to a tremendous computational cost, and this is by far the dominant cost for these problems. Several authors have proposed randomization and stochastic programming techniques to drastically reduce the number of system solves by estimating the objective function using only a few appropriately chosen random linear combinations of the sources. While some have reported good solution quality at a greatly reduced cost, for our problem of interest, diffuse optical tomography, the approach often does not lead to sufficiently accurate solutions. We propose two improvements. First, to efficiently exploit Newton-type methods, we modify the stochastic estimates to include random linear combinations of detectors, drastically reducing the number of adjoint solves. Second, after solving to a modest tolerance, we compute a few simultaneous sources and detectors that maximize the Frobenius norm of the sampled Jacobian to improve the rate of convergence and obtain more accurate solutions. We complement these optimized simultaneous sources and detectors by random simultaneous sources and detectors constrained to a complementary subspace. Our approach leads to solutions of the same quality as obtained using all sources and detectors but at a greatly reduced computational cost, as the number of large-scale linear systems to be solved is significantly reduced.