Two improvements of the fast iterative shrinkage/thresholding algorithm : Overrelaxation and weak convergence

概要

論文の詳細を見る
In this paper, we present two improved schemes of FISTA (an iterative gradient-based algorithm, whose convergence rate of the objective function is Ο(1/k^2} in term of the iteration counter k) for the minimization of the sum of a smooth and a nonsmooth convex function. Such minimization problems arise naturally in signal and image processing. Our two schemes overcome two limitations of FISTA: (i) The stepsize in the for ward-back ward splitting step in FISTA is bounded by a constant value determined by the Lipschitz constant of the gradient of the smooth function and (ii) no results on weak convergence of FISTA to a solution had been presented to our best knowledge. The first scheme admits variable stepsizes in broader ranges than FISTA while keeping the same convergence rate Ο(1/k^2) of the objective function. The second scheme, whose convergence rate of the objective function is not guaranteed as Ο(1/k^2), converges weakly to a solution by using a sequence generated by FISTA. A numerical example demonstrates the effectiveness of each improvement by showing that the proposed schemes outperform conventional algorithms in terms of speed of convergence.
2011-02-24