# Conjugate Gradient Hard Thresholding Pursuit Algorithm for Sparse Signal Recovery
## 2 Literature Review  
In the past decade, a series of iterative greedy algorithms has been proposed to directly solve Equation (1). These algorithms have been attracting increased attention due to their low algorithm complexity and good reconstruction performance. According to the support set selection strategy used in the iteration process, we can roughly classify the family of iterative greedy algorithms into three categories.  
(1) orthogonal matching pursuit (OMP) [17]-based OMP-like algorithms, such as compressive sampling matching pursuit (CoSaMP), subspace pursuit (SP) [18], regularized orthogonal matching pursuit (ROMP) [19], generalized orthogonal matching pursuit (GOMP) [20], sparsity adaptive matching pursuit (SAMP) [21], stabilized orthogonal matching pursuit (SOMP) [22], perturbed block orthogonal matching pursuit (PBOMP) [23] and forward backward pursuit (FBP) [24]. A common feature of these algorithms is that in each iteration, a support set is determined to approximate the correct support set according to the correlation value between the measurement vector \(\mathbf{y}\) and the columns of \(\mathbf{A}\).  
(2) iterative hard thresholding (IHT)-based IHT-like algorithms, such as NIHT, accelerated iterative hard thresholding (AIHT) [25], conjugate gradient iterative hard thresholding (CGIHT) [26; 27]. Unlike the OMP-like algorithm, the approximate support set for the \(n\)th iteration of IHT-like algorithms is determined by the value of \(\mathbf{A}^{\text{T}}\mathbf{y}+(\mathbf{I}-\mathbf{A}^{\text{T}}\mathbf{A})\mathbf{x}_{n-1}\), which is closer to the correct support set than using the values of \(\mathbf{A}^{\text{T}}\mathbf{y}\)[28].  
(3) algorithms composed of OMP-like and IHT-like algorithms, such as Hard Thresholding Pursuit (HTP) [28; 29], generalized hard thresholding pursuit (GHTP) [30], \(\ell_{0}\) regularized HTP [31], Partial hard thresholding (PHT) [32] and subspace thresholding pursuit (STP) [33]. OMP-like algorithms use least squares to update sparse coefficients in each iteration, which plays a role in debiasing and makes it approach the exact solution quickly. However, it is well known that the least squares are time-consuming, which leads to a high complexity of single iteration. The advantage of IHT-like algorithms are the simple iteration operation and good support set selection strategy, but it needs more iterations. By combining the OMP-like algorithm and the IHT-like algorithm, these algorithms absorb the advantages of the above two kinds of algorithms, and have strong theoretical guarantees and good empirical performance [29].  
Among the above algorithms, CoSaMP and SP do not provide a better theoretical guarantee than the IHT algorithm, but their empirical performance is better than IHT. The simple combination of CoSaMP and IHT algorithm lead to the HTP algorithm whose convergence requires fewer number of iterations than IHT algorithm. However, the reconstruction performance of HTP is greatly affected by the step size and an optimal step size is difficult to determine in practical applications, which may cause the HTP to converge slowly when selecting an inappropriate step size. Furthermore, although the HTP algorithm only requires a small number of iterations to converge to the exact vector \(\mathbf{x}\), it only uses a single gradient descent direction as the search direction in iterative progress, which may not be the best choice for general optimization problems. In [26], conjugate gradient method was used to accelerate the convergence of IHT algorithm due to its fast convergence rate. In this paper, inspired by the HTP algorithm and CGIHT algorithm, the operations of these two algorithms in each iteration is combined to take advantage of both.  
In this paper, we first introduce the idea of the CGHTP algorithm, then analyze the convergence of the proposed algorithm, and finally validate the proposed algorithm with synthetic experiments and real-world image reconstruction experiments.