On the regularity of fixed-point iterations and practical convergence results

Abstract

In ill-posed inverse problems, one is often very happy when a given regularization scheme converges rapidly (in some sense) to the exact solution as some regularization parameter converges to zero. It is taken for granted that algorithms for solving the regularized problem converge rapidly to the regularized solution. We show that this assumption cannot be taken for granted and examine more closely the regularity requirements for local linear convergence of fundamental algorithms such as the method of alternating projections, steepest descents and the Douglas-Rachford algorithm. Linear convergence in particular is important for iteratively regularized schemes since this provides principled stopping criteria; until recently, the focus has been only on convergence. Our goal is to determine the weakest conditions possible in order to achieve local linear convergence, and use this information to inform reguarization schemes. We demonstrate an application of the theory to the problem of phase retrieval in diffractive X-ray imaging.