IML FISTA: A Multilevel Framework for Inexact and Inertial Forward-Backward. Application to Image Restoration

This paper presents a multilevel framework for inertial and inexact proximal algorithms, that encompasses multilevel versions of classical algorithms such as forward-backward and FISTA. The methods are supported by strong theoretical guarantees: we prove both the rate of convergence and the convergence of the iterates to a minimum in the convex case, an important result for ill-posed problems. We propose a particular instance of IML (Inexact MultiLevel) FISTA, based on the use of the Moreau envelope to build efficient and useful coarse corrections, fully adapted to solve problems in image restoration. Such a construction is derived for a broad class of composite optimization problems with proximable functions. We evaluate our approach on several image reconstruction problems and we show that it considerably accelerates the convergence of the corresponding one-level (i.e. standard) version of the methods, for large-scale images.