A scaled, inexact and adaptive Fast Iterative Soft-Thresholding Algorithm for convex image restoration

In this note, we consider a special instance of the scaled, inexact and adaptive generalised Fast Iterative Soft-Thresholding Algorithm (SAGE-FISTA) recently proposed in [15] for the efficient solution of strongly convex composite optimisation problems. In particular, we address here the sole (non-strongly) convex optimisation scenario, which is frequently encountered in many imaging applications. The proposed inexact S-FISTA algorithm shows analogies to the variable metric and inexact version of FISTA studied in [6], the main difference being the use of an adaptive (non-monotone) backtracking strategy allowing for the automatic adjustment of the algorithmic step-size along the iterations (see [8], [17]). A quadratic convergence result in function values depending on the backtracking parameters and the upper and lower bounds on the spectrum of the variable metric operators is given. Experimental results on TV image deblurring problems with Poisson noise are then reported for numerical validation, showing improved computational efficiency and precision.

I. Introduction

The use of forward-backward (FB) algorithms is nowadays extremely popular in the context of variational imaging due to their easy applicability in many problems and their provable fast convergence when coupled with suitable inertial updates, as in the case of the celebrated Fast Iterative Soft-Thresholding Algorithm (FISTA) [1]. Their successful application relies, in particular, on some practical assumptions on the composite energy minimization problem one aims to solve. First, a closed-form computation of the backward (proximal) step is desirable to avoid the use of inner solvers. Secondly, an accurate estimation of the ‘steepness’ of the smooth component of the functional to minimize is required to provide a sufficiently meaningful forward update, thus avoiding an unnecessary large number of iterations till convergence. Whenever either (or both) of these two features is missing, the practical effectiveness of FB-type algorithms may be limited. To circumvent the former issue, recent approaches deal directly with the inexact calculation of the proximal point and provide appropriate conditions on the accuracy of these approximations which guarantee the same convergence properties of FISTA, see, e.g., [4], [6]. In order to deal with the latter bottleneck, adaptive backtracking procedures favouring the adjustment of the algorithmic step-size along the iterations can be used, see, e.g., [8], [17]. Moreover, as previous studies in the context of smooth convex optimisation problems showed [14], FB algorithms may also benefit from suitable scaling approaches defined in terms of second-order (Newton-type) information. Such procedures have been shown to render particularly effective in the context of signal-dependent image reconstruction problems in a variety of applications ranging from biological to astronomical imaging, see e.g., [2]. Recently, in [15] the authors proposed a general inexact, scaled and adaptive FISTA-type algorithm (named there SAGE-FISTA) designed for solving possibly strongly-convex composite problems and encompassing all the aforementioned approaches. Upon suitable conditions on the scaling updates and on the inexactness parameters sequence, accelerated convergence rates for the function values are there rigorously proved.