On the rate of convergence of the proximal alternating linearized minimization algorithm for convex problems

We analyze the proximal alternating linearized minimization algorithm (PALM) for solving non-smooth convex minimization problems where the objective function is a sum of a smooth convex function and block separable non-smooth extended real-valued convex functions. We prove a global non-asymptotic sublinear rate of convergence for PALM. When the number of blocks is two, and the smooth coupling function is quadratic we present a fast version of PALM which is proven to share a global sublinear rate efficiency estimate improved by a squared root factor. Some numerical examples illustrate the potential benefits of the proposed schemes.