We consider the problem of minimizing the sum of a convex function and a convex function composed with an injective linear mapping. For such problems, subject to a coercivity condition at fixed points of the corresponding Picard iteration, iterates of the alternating directions method of multipliers converge locally linearly to points from which the solution to the original problem can be computed. Our proof strategy uses duality and strong metric subregularity of the Douglas--Rachford fixed point mapping. Our analysis does not require strong convexity and yields error bounds to the set of model solutions. We show in particular that convex piecewise linear-quadratic functions naturally satisfy the requirements of the theory, guaranteeing eventual linear convergence of both the Douglas--Rachford algorithm and the alternating directions method of multipliers for this class of objectives under mild assumptions on the set of fixed points. We demonstrate this result on quantitative image deconvolution and denoising with multiresolution statistical constraints.

We propose a general alternating minimization algorithm for nonconvex optimization problems with separable structure and nonconvex coupling between blocks of variables. To fix our ideas, we apply the methodology to the problem of blind ptychographic imaging. Compared to other schemes in the literature, our approach differs in two ways: (i) it is posed within a clear mathematical framework with practical verifiable assumptions, and (ii) under the given assumptions, it is provably convergent to critical points. A numerical comparison of our proposed algorithm with the current state of the art on simulated and experimental data validates our approach and points toward directions for further improvement.

Improvements in electromagnetic sources, detectors, optical components, and computational imaging have made it possible to achieve three-dimensional atomic-scale resolution using tomographic phase-contrast imaging techniques. These greater capabilities have placed a premium on improving the efficiency and stability of phase retrieval algorithms for recovering the missing phase information in diffraction observations. In some cases, so called direct methods suffice, but, for large macromolecules and nonperiodic structures, one must rely on numerical techniques for reconstructing the missing phase. This is the principal motivation of our work. We report on recent progress in algorithms for iterative phase retrieval. The theory of convex optimisation is used to develop and to gain insight into counterparts for the nonconvex problem of phase retrieval. We propose a relaxation of averaged alternating reflectors and determine the fundamental mathematical properties of the related operator in the convex case. Numerical studies support our theoretical observations and demonstrate the effectiveness of the newer generation of algorithms compared to the current state of the art.

A fundamental problem in scattering theory is to reconstruct the scattered field on a given region from knowledge of the wave on a surface in the far field. A recent methodology which we call point source methods has been developed and applied to the reconstruction of impenetrable obstacles. In this work we present the application of point source methods to the reconstruction of the scattered acoustic field from far field measurements of an unknown penetrable inhomogeneous medium illuminated by a single plane wave.

The state of the art for solving the phase retrieval problem in two dimensions relies heavily on the algorithms proposed by Gerchbercy, Saxton, and Fienup. Despite the widespread use of these algorithms, current mathematical theory cannot explain their remarkable success. It is already known that the Gerchberg-Saxton algorithm is a nonconvex version of method of alternating projections. In this paper, we show that two other prominent phase retrieval methods also have well known counterparts in the world of convex optimization algorithms: Fienup's basic input-output algorithm corresponds to Dykstra's algorithm, and Fienup's hybrid input-output algorithm can be viewed as an instance of the Douglas-Rachford algorithm. This work provides a theoretical framework to better understand and, potentially, improve existing phase recovery algorithms.