Large sparse signal recovery by conjugate gradient algorithm based on smoothing technique

Finding sparse solutions to under-determined linear systems of equations have intensively involved in fields of machine learning, signal processing, compressive sensing, linear inverse problems and statistical inference. Generally, the task can be realized by solving ℓ1ℓ1-norm regularized minimization problems. However, the resulting problem is challenging due to the non-smoothness of the regularization term. Inspired by Nesterov’s smoothing technique, this paper proposes, analyzes and tests a modified Polak–Ribière–Polyak conjugate gradient method to solve large-scale ℓ1ℓ1-norm least squares problem for sparse signal recovery. The per-iteration cost of the proposed algorithm is dominated by three matrix–vector multiplications and the global convergence is guaranteed by results in optimization literature. Moreover, the algorithm is also accelerated by continuation loops as usual. The limited experiments show that this continuation technique benefits to its performance. Numerical experiments which decode a sparse signal from its limited measurements illustrate that the proposed algorithm performs better than NESTA—a recently developed code with Nesterov’s smoothing technique and gradient algorithm.