Incomplete variables truncated conjugate gradient method for signal reconstruction in compressed sensing

Compressed sensing (CS) has stirred great interests in many fields of science, due to its ability to capture most information of compressible signals at a rate significantly below the Nyquist rate. Reconstructing the signal from random measurements is an important topic in CS. In this paper, a new algorithm— Incomplete variables Truncated Conjugate Gradient method   (ITCG) is proposed to reconstruct the signal by solving a programming with ℓ1ℓ1 norm. By adjusting the parameters of ITCG, two specific algorithms are presented, i.e. ITCG-vs for very sparse reconstruction and ITCG-nvs for not very sparse reconstruction. To make full use of the sparse nature of signals, ITCG can reconstruct them efficiently. The experiments show that the two algorithms of ITCG (especially ITCG-nvs) are much faster than competing methods in sparse reconstruction. In addition, it has been shown that ITCG-vs can converge after finite iterations under some decent conditions.