Multilevel preconditioning for sparse optimization of functionals with nonconvex fidelity terms

This paper is concerned with the development of numerical schemes for the minimization of functionals involving sparsity constraints and nonconvex fidelity terms. These functionals appear in a natural way in the context of Tikhonov regularization of nonlinear inverse problems with ℓ₁ penalty terms. Our method of minimization is based on a generalized conditional gradient scheme. It is well known that these algorithms might converge quite slowly in practice. Therefore, we propose an acceleration which is based on a decreasing thresholding strategy. Its efficiency relies on certain spectral properties of the problem at hand. We show that under certain boundedness and contraction conditions the resulting algorithm is linearly convergent to a global minimizer and that the iteration is monotone with respect to the Tikhonov functional. We study important classes of operator equations to which our analysis can be applied. Moreover, we introduce a certain multilevel preconditioning strategy which in practice promotes the aforementioned spectral properties for problems where the nonlinearity is a perturbation of a linear operator.