Quantifying convergence of Picard iterations

08.11.2017 16:15 - 17:15

D. Russell Luke (Universität Göttingen)

It can be observed in many applications that algorithms converge unexpectedly well, despite any theory
 to explain their success.  An analysis of algorithm complexity in terms of function values is wide-spread
 and can be applied readily in many practical instances.  However, this strategy of analysis cannot explain
 the observed convergence to stationary points of iterates in many cases, nor can it yield error
 estimates on the distance to locally optimal solutions as opposed to locally optimal values.
 We propose a framework for quantifiable local convergence analysis of iterations of expansive
 fixed point mappings.   Application of the theory involves verifying two key properties of fixed point mappings near fixed points:  almost nonexpansiveness (usually easy) and the existence of an error bound (usually hard).

To demonstrate the theory, we prove for the first time a number of results showing local linear convergence of cyclic projections for (possibly) inconsistent feasibility problems, local linear convergence of the forward-
 backward algorithm for structured optimization without convexity, strong or otherwise, and local
 linear convergence of a nonconvex application of the Douglas–Rachford algorithm for minimization.
 Known results, convex and nonconvex, are recovered in this framework.  Concrete application to
 inverse problems in x-ray imaging and sub-diffraction florescence mircroscopy are presented.

R. Bot

Sky Lounge, 12. OG, OMP 1