- Convergence Rates with Inexact Nonexpansive Operators Jingwei Liang (jingwei.liangensicaen.fr) Jalal Fadili (jalal.Fadiliensicaen.fr) Gabriel Peyré (gabriel.Peyreceremade.dauphine.fr) Abstract: In this paper, we present a convergence rate analysis for the inexact Krasnosel'ski{\u{\i}}-Mann iteration built from nonexpansive operators. Our results include two main parts: we first establish global pointwise and ergodic iteration-complexity bounds, and then, under a metric subregularity assumption, we establish local linear convergence for the distance of the iterates to the set of fixed points. The obtained iteration-complexity result can be applied to analyze the convergence rate of various monotone operator splitting methods in the literature, including the Forward-Backward, the Generalized Forward-Backward, Douglas-Rachford, ADMM and Primal-Dual splitting (PDS) methods. For these methods, we also develop easily verifiable termination criteria for finding an approximate solution, which can be seen as generalization of the termination criterion for the classical gradient descent method. We finally develop a parallel analysis for the non-stationary iteration. The usefulness of our results is illustrated by applying them to a large class of composite convex optimization problems of the form $f + \sum_{i=1}^n h_i$, where $f$'s gradient is Lipschitz-continuous and the $h_i$'s are simple (\ie~whose proximity operator is easily computable). Experiments on some inverse problems in signal and image processing problems are shown. Keywords: Monotone inclusion, Nonexpansive operator, Convergence rates, Operator splitting, Convex optimization, Inverse problems. Category 1: Convex and Nonsmooth Optimization Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: GREYC CNRS UMR 6072, ENSICAEN, 6, Bd du Maréchal Juin, 14050 Caen Cedex, France, 04/2014 Download: [PDF]Entry Submitted: 04/18/2014Entry Accepted: 04/18/2014Entry Last Modified: 06/11/2014Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.