A fast and adaptive algorithm for the inverse medium problem with multiple frequencies and multiple sources for the time-harmonic wave equation

We consider the inverse medium problem for the time-harmonic wave equation with broadband and multipoint illumination in the low frequency regime. Such a problem finds many applications in geosciences (e.g. ground penetrating radar), non-destructive evaluation (acoustics), and medicine (optical tomography). We use an integralequation (Lippmann-Schwinger) formulation, which we discretize using a quadrature method. We consider only small perturbations of the background medium (Born approximation). To solve this inverse problem, we use a least squares formulation that is regularized with the truncated Singular Value Decomposition (SVD). If N-omega is the number of excitation frequencies, N-s the number of incoming waves, N-d the number of detectors, and N the parameterization for the scatterer, a dense singular value decomposition for the overall input-output map will have [min(NsN omega N-d, N)](2) xmax(NsN omega Nd, N) cost. We have developed a fast SVD approach that brings the cost down to O(NN omega Nd + NN omega Ns) thus, providing orders of magnitude improvements over a black-box dense SVD. In the second part of this contribution, we propose an adaptive algorithm in space to optimize the ratio between the number of points and the accuracy. The method uses an octree to drive the computation. The refinement criterion is derived from the method used for the detection of edges in piecewise smooth functions, from their spectral data.