# Conjugate Gradient Hard Thresholding Pursuit Algorithm for Sparse Signal Recovery
## 3 Conjugate Gradient Hard Thresholding Pursuit Algorithm
According to whether the support sets of the previous and current iterations are equal, one of the two directions is selected as the search direction. In addition, then the support set is updated by solving a least square problem. In addition, CGHTP provides a way to choose the best step size while ensuring convergence. The HTP algorithm uses the gradient direction as the search direction, which has a linear asymptotic convergence rate related to \((\kappa-1)/(\kappa+1)\), where \(\kappa\) is the condition number of the matrix \(A_{\text{supp}(\mathbf{x}_{n})}^{\mathsf{T}}A_{\text{supp}(\mathbf{x}_{n})}\). Owing to the superlinear asymptotic convergence speed with a rate given by \((\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)\)[24], conjugate gradient method has been applied to accelerate the convergence rate in CGHTP algorithm. CGHTP draws on the advantages of the CGHTP algorithm. If \(T_{n}=T_{n-1}\), it means that the correct support set is identified and the submatrix \(\mathbf{A}_{T_{n}}\) is no longer changed, CG method is applied to solve the overdetermined system \(A_{T_{n}}^{\mathsf{T}}\mathbf{A}_{T_{n}}\mathbf{x}_{n}=\mathbf{A}_{T_{n}}^{\mathsf{T}}\mathbf{y}\), and the convergence rate may be superlinear with a rate given by \((\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)\). ```
Input:\(\mathbf{A},\mathbf{y},s\) Initialization:\(\mathbf{x}_{0}=0\), \(T_{0}=\emptyset\). for each iteration \(n\geq 1\)do 1) \(\mathbf{\hat{x}}_{n}=\mathbf{x}_{n-1}+\mathbf{A}^{\mathsf{T}}(\mathbf{y}-\mathbf{A}\mathbf{x}_{n-1})\) 2) \(T_{n}=\text{supp}(H_{s}(\mathbf{\hat{x}}_{n}))\) 3) \(\mathbf{x}_{n}=\text{arg}\min_{\mathbf{z}\in\mathbb{R}^{N}}\{\|\mathbf{y}-\mathbf{A}\mathbf{z}\|_{ 2},\quad\text{supp}(\mathbf{z})\subseteq T_{n}\}\) 4) update the residual \(\mathbf{r}_{n}=\mathbf{y}-\mathbf{A}\mathbf{x}_{n}\) until the stopping criteria is met endfor
```  
**Algorithm 1**[20] Hard Thresholding Pursuit  
Figure 3: Block diagram of CGHTP algorithm. \(T_{n}\) is the support set of \(\mathbf{x}\) in the \(n\)th iteration, “LSM” denotes least square method. ```
Input:\(A\), \(\mathbf{y}\), \(s\), Initialization:\(\mathbf{x}_{0}=0\), \(T_{-1}=\varnothing\), \(\mathbf{d}_{-1}=0\), \(T_{0}=\text{supp}(H_{s}(\mathbf{A}^{\text{T}}\mathbf{y}))\). for each iteration \(n\geq 0\)do
1) \(\mathbf{g}_{n}=\mathbf{A}^{\text{T}}(\mathbf{y}-\mathbf{A}\mathbf{x}_{n})\) (compute gradient direction)
2) if\(T_{n}\
eq T_{n-1}\)then \(\alpha_{n}=\left\langle\mathbf{g}_{\text{T}_{n}},\mathbf{g}_{\text{T}_{n}}\right\rangle \big{/}\langle\mathbf{A}_{T_{n}}\mathbf{g}_{\text{T}_{n}},\mathbf{A}_{T_{n}}\mathbf{g}_{\text{T }_{n}}\rangle\) if\(\alpha_{n}\geq c\|\tilde{\mathbf{x}}_{n+1}-\mathbf{x}_{n}\|_{2}^{2}\Big{/}\|A(\tilde{\mathbf{x}}_{n +1}-\mathbf{x}_{n})\|_{2}^{2}\)then  execute loop \(\alpha_{n}\leftarrow\alpha_{n}/\eta\) until (adaptively select step size) \(\alpha_{n}<\|\tilde{\mathbf{x}}_{n+1}-\mathbf{x}_{n}\|_{2}^{2}\Big{/}\|\mathbf{A}(\tilde{ \mathbf{x}}_{n+1}-\mathbf{x}_{n})\|_{2}^{2}\) \(\tilde{\mathbf{x}}_{n+1}=H_{s}(\mathbf{x}_{n}+\alpha_{n}\mathbf{d}_{n})\), \(T_{n+1}=\text{supp}(\tilde{\mathbf{x}}_{n+1})\)  end end
3) if\(T_{n}=T_{n-1}\)then \(\beta_{n}=-\frac{\langle A_{T_{n}}\mathbf{g}_{\text{T}_{n}}\mathbf{A}_{T_{n}}\mathbf{d}_{n -1T_{n}}\rangle}{\langle A_{T_{n}}\mathbf{d}_{n-1T_{n}},A_{T_{n}}\mathbf{d}_{n-1T_{n}} \rangle}\) \(\mathbf{d}_{n}=\mathbf{g}_{n}+\beta_{n}\mathbf{d}_{n-1}\) (compute conjugate gradient direction) \(\alpha_{n}=\left\langle\mathbf{g}_{\text{T}_{n}},\mathbf{g}_{\text{T}_{n}}\right\rangle \big{/}\langle A_{T_{n}}\mathbf{d}_{nT_{n}},\mathbf{A}_{T_{n}}\mathbf{d}_{nT_{n}}\rangle\) (compute optimal step size) \(\tilde{\mathbf{x}}_{n+1}=H_{s}(\mathbf{x}_{n}+\alpha_{n}\mathbf{d}_{n})\), \(T_{n+1}=\text{supp}(\tilde{\mathbf{x}}_{n+1})\)  end if \(\mathbf{x}_{n+1}=\arg\min\left\{\|\mathbf{y}-\mathbf{A}\mathbf{z}\|_{2},\text{supp}(\mathbf{z}) \subseteq T_{n+1}\right\}\) endfor Output:\(\mathbf{x_{n+1}}\), \(T_{n+1}\)
```  
**Algorithm 3** Conjugate Gradient Hard Thresholding Pursuit