Accelerated projected steepest descent method for nonlinear inverse problems with sparsity constraints

Abstract

This paper is concerned with the construction of an iterative algorithm to solve nonlinear inverse problems with an ℓ1 constraint on x. One extensively studied method to obtain a solution of such an ℓ1 penalized problem is iterative soft-thresholding. Regrettably, such iteration schemes are computationally very intensive. A subtle alternative to iterative soft-thresholding is the projected gradient method that was quite recently proposed by Daubechies et al (2008 J. Fourier Anal. Appl. 14 764–92). The authors have shown that the proposed scheme is indeed numerically much thriftier. However, its current applicability is limited to linear inverse problems. In this paper we provide an extension of this approach to nonlinear problems. Adequately adapting the conditions on the (variable) thresholding parameter to the nonlinear nature, we can prove convergence in norm for this projected gradient method, with and without acceleration. A numerical verification is given in the context of nonlinear and non-ideal sensing. For this particular recovery problem we can achieve an impressive numerical performance (when comparing it to non-accelerated procedures).