Browsing by Author "Combettes, Patrick L."

A new iterative method for finding the projection onto the intersection of two closed convex sets in a Hilbert space is presented. It is a Haugazeau-like modification of a recently proposed averaged alternating reflections method which produces a strongly convergent sequence.

We consider the problem of finding a best approximation pair, i.e., two points which achieve the minimum distance between two closed convex sets in a Hilbert space. When the sets intersect, the method under consideration, termed AAR for averaged alternating reflections, is a special instance of an algorithm due to Lions and Mercier for finding a zero of the sum of two maximal monotone operators. We investigate systematically the asymptotic behavior of AAR in the general case when the sets do not necessarily intersect and show that the method produces best approximation pairs provided they exist. Finitely many sets are handled in a product space, in which case the AAR method is shown to coincide with a special case of Spingarn's method of partial inverses.

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.