On the convergence rates of proximal splitting algorithms

In this work, we first provide iteration-complexity bounds (pointwise and ergodic) for the inexact Krasnosel´skî-Mann iteration built from nonexpansive operators. Moreover, under an appropriate regularity assumption on the fixed point operator, local linear convergence rate is also established. These results are then applied to analyze the convergence rate of various proximal splitting methods in the literature, which includes the Forward-Backward, generalized Forward-Backward, Douglas-Rachford, ADMM and some primal-dual splitting methods. For these algorithms, we develop easily verifiable termination criteria for finding an approximate solution, which is a generalization of the termination criterion for the classical gradient descent method. We illustrate the usefulness of our results on a large class of problems in signal and image processing.