# Conjugate Gradient Hard Thresholding Pursuit Algorithm for Sparse Signal Recovery
## 3 Conjugate Gradient Hard Thresholding Pursuit Algorithm  
Firstly, we make a simple summary of the HTP algorithm and the CGIHT algorithm to facilitate an intuitive understanding of the proposed algorithm. The pseudo-codes of HTP and CGIHT are shown in Algorithms 1 and 2, respectively. In [20], the debiasing step in the OMP-like algorithms and the estimation step in the IHT-like algorithms are coupled in an algorithm to form the HTP algorithm. The HTP algorithm has excellent reconstruction performance as well as strong theoretical guarantee in terms of the RIP. Optimizing search direction in each iteration is the main innovation of HTP algorithm. It fully considers that in the iterative process, when the subspace determined by the support set is consistent, the conjugate gradient (CG) method [23] can be employed to accelerate the convergence rate. Two versions of CGIHT algorithms for CS are provided in [19], one of them, the algorithm called CGIHT restarted for CS is summarized in Algorithm 2. The iteration procedures of CGIHT and CGIHT restarted differ in their selection of search directions. CGIHT algorithm uses the conjugate gradient respect to \(\mathbf{A}_{T}^{\mathrm{T}}\mathbf{A}\) as the search direction in all iteration, while CGIHT restarted determines the search direction according to whether the support set of the current iteration is equal to that of the previous iteration. Inspired by the respective advantages of HTP and CGIHT algorithms, we present the CGHTP algorithm in this section. A simple block diagram of the CGHTP algorithm can be seen in Figure 3. The algorithm enters an iterative loop after inputting the initialized data. The loop process updates the \(\mathbf{x}_{n}\) and support set \(T_{n}\) in two alternative ways, one of which is the combination of the gradient descent method and the adaptive step size selection method, and the other is the CG method. The selection criteria for these two ways is to determine whether the support sets of two adjacent iterations are equal. If the support set of the previous iteration is equal to that of the current iteration, then the gradient descent method is used. If not, the CG method is used [34]. All candidate solutions and candidate support sets obtained through these ways are finally updated by the least square method. The main characteristic of the proposed CGHTP algorithm is that the support set selection strategy of HTP is combined with the acceleration strategy of CGIHT restarted algorithm in one algorithm. The main steps of CGHTP are listed in Algorithm 3. Similar to CGIHT, CGHTP is initialized with \(\mathbf{x}=0\), \(T_{-1}=\text{supp}(H_{s}(\mathbf{A}^{\mathrm{T}}\mathbf{y}))\). The main body of CGHTP mainly includes the following steps. In Step 1), the gradient direction of the cost function \(\|\mathbf{y}-\mathbf{A}\mathbf{x}_{n}\|_{2}^{2}\)[16] in the current iteration is solved to calculate the subsequent step size \(\alpha_{n}\). In Step 2), if \(\tilde{\mathbf{x}}_{n+1}\) has a different support from the previous estimate, i.e., \(T_{n}\
eq T_{n-1}\), similar to the convergence criterion used in NIHT algorithm, \(c\|\tilde{\mathbf{x}}_{n+1}-\mathbf{x}_{n}\|_{2}^{2}\Big{/}\|\mathbf{A}(\tilde{\mathbf{x}}_{n +1}-\mathbf{x}_{n})\|_{2}^{2}\) is used to check whether the step size is smaller than it, where \(c\) is a small fixed constant and \(0<c<1\). If this holds, continue to run the next steps. Otherwise the step size is continuously reduced by looping \(\alpha_{n}\leftarrow\alpha_{n}/\eta\) until the convergence criterion is met, here \(0<\eta<1\). In Step 3), if \(T_{n}=T_{n-1}\), the CG direction is used as the search direction. Finally, Step 4) updates \(\mathbf{x}_{n+1}\) by solving a least square problem. Compared to the HTP algorithm, the CGHTP algorithm provides two search directions in the iterative process, including the gradient direction \(\mathbf{g}_{n}\) of the cost function \(\|\mathbf{y}-\mathbf{A}\mathbf{x}_{n}\|_{2}^{2}\) and the CG direction \(\mathbf{d}_{n}\).