Derivative-free MLSCD conjugate gradient method for sparse signal and image reconstruction in compressive sensing

Abstract

Finding sparse solution to under-determined or ill-condition equations is a fundamental problem encountered in most applications arising from linear inverse problem, compressive sensing, machine learning and statistical inference. In this paper, inspired by the reformulation of the $\ell_1$-norm regularized minimization problem into a convex quadratic program problem by Xiao et al. (Nonlinear Analysis: Theory, Methods \& Applications, 74(11), 3570-3577), we propose, analyze, and test a derivative-free conjugate gradient method to solve the $\ell_1$-norm problem arising from the reconstruction of sparse signal and image in compressive sensing. The method combines the MLSCD conjugate gradient method proposed for solving unconstrained minimization problem by Predrag et al. (Journal of Optimization Theory and Applications, 178(3), 860-884) and a line search method. Under some mild assumptions, the global convergence of the proposed method is established using the backtracking line search. Computational experiments are carried out to reconstruct sparse signal and image in compressive sensing. The numerical result indicates that the proposed method is stable, accurate and robust.