Solving Large-Scale Inverse Problems via Approximate Message Passing and Optimization

This work studies the problem of reconstructing a signal from measurements obtained by a sensing system, where the measurement model that characterizes the sensing system may be linear or nonlinear. We first consider linear measurement models. In particular, we study the popular low-complexity iterative linear inverse algorithm, approximate message passing (AMP), in a probabilistic setting, meaning that the signal is assumed to be generated from some probability distribution, though the distribution may be unknown to the algorithm. The existing rigorous performance analysis of AMP only allows using a separable or block-wise separable estimation function at each iteration of AMP, and therefore cannot capture sophisticated dependency structures in the signal. This work studies the case when the signal has a Markov random field (MRF) prior, which is commonly used in image applications. We provide rigorous performance analysis of AMP with a class of non-separable sliding-window estimation functions, which is suitable to capture local dependencies in an MRF prior. In addition, we design AMP-based algorithms with non-separable estimation functions for hyperspectral imaging and universal compressed sensing (imaging), and compare our algorithms to state-of-the-art algorithms with extensive numerical examples. For fast computation in largescale problems, we study a multiprocessor implementation of AMP and provide its performance analysis. Additionally, we propose a two-part reconstruction scheme where Part 1 detects zero-valued entries in the signal using a simple and fast algorithm, and Part 2 solves for the remaining entries using a high-fidelity algorithm. Such two-part scheme naturally leads to a trade-off analysis of speed and reconstruction quality. Finally, we study diffractive imaging, where the electric permittivity distribution of an object is reconstructed from scattered wave measurements. When the object is strongly scattering, a nonlinear measurement model is needed to characterize the relationship between the permittivity and the scattered wave. We propose an inverse method for nonlinear diffractive imaging. Our method is based on a nonconvex optimization formulation. The nonconvex solver used in the proposed method is our new variant of the popular convex solver, fast iterative shrinkage/ thresholding algorithm (FISTA). We provide a fast and memory-efficient implementation of our new FISTA variant and prove that it reliably converges for our nonconvex optimization problem. Hence, our new FISTA variance may be of interest on its own as a general nonconvex solver. In addition, we systematically compare our method to state-of-the-art methods on simulated as well as experimentally measured data in both 2D and 3D (vectorial field) settings