# Conjugate Gradient Hard Thresholding Pursuit Algorithm for Sparse Signal Recovery
## 4 Convergence Analysis of CGHTP  
In this section, we analyze the convergence of the proposed algorithms. We give a simple proof that the CGHTP algorithm converges to the exact solution of (1) after a finite number of iterations when the measurement matrix \(\mathbf{A}\) satisfies some conditions. In Algorithm 3, when \(T_{n}\
eq T_{n-1}\) and \(\alpha_{n}\leq c\|\tilde{\mathbf{x}}_{n+1}-\mathbf{x}_{n}\|_{2}^{2}\Big{/}\|\mathbf{A}( \tilde{\mathbf{x}}_{n+1}-\mathbf{x}_{n})\|_{2}^{2}\), the iterative process of the CGHTP algorithm is equivalent to the HTP algorithm. Similar to Lemma 3.1 in [20], we obtain the following lemma:  
**Lemma 1**. : _The sequences defined by CGHTP eventually periodic._  
**Theorem 1**. : _The sequence \((\mathbf{x}_{n})\) generated by CGHTP algorithm converges to \(\mathbf{x}\) in a finite number of iterations, where \(\mathbf{x}\) denotes the exact solution of (1)_  
The proof of Theorem 1 is partitioned here into two steps. The first step is that when the current support set is not equal to the previous support set, the orthogonal factor \(\beta\) is equal to \(0\). At this time, the CGHTP algorithm reduces to the HTP algorithm, so their convergence is the same. The second step is that when the two support sets are equal, the step size is related to the orthogonal factor and the CG direction. Detailed proof is given below. Proof of Theorem 1.: When \(T_{n}\
eq T_{n-1}\), according to Algorithm 3, \(\tilde{\mathbf{x}}_{n+1}=H_{s}(\mathbf{x}_{n}+\alpha_{n}\mathbf{g}_{n})\) and \(T_{n+1}=\text{supp}(\tilde{\mathbf{x}}_{n+1})\), since \(\mathbf{x}_{n+1}=\arg\min\left\{\|\mathbf{y}-\mathbf{A}\mathbf{z}\|_{2},\text{supp}(\mathbf{z}) \subseteq T_{n+1}\right\}\), one has  
\[ \begin{array}{l}\|\mathbf{y}-\mathbf{A}\mathbf{x}_{n+1}\|_{2}^{2}-\|\mathbf{y}-\mathbf{A}\mathbf{x}_{n} \|_{2}^{2}\leq\|\mathbf{y}-\mathbf{A}\tilde{\mathbf{x}}_{n+1}\|_{2}^{2}-\|\mathbf{y}-\mathbf{A}\mathbf{x }_{n}\|_{2}^{2}\\ \hskip 14.226378 pt=\|\mathbf{y}-\mathbf{A}\mathbf{x}_{n}+\mathbf{A}(\mathbf{x}_{n}-\tilde{\mathbf{x}}_{n+ 1})\|_{2}^{2}-\|\mathbf{y}-\mathbf{A}\mathbf{x}_{n}\|_{2}^{2}\\ \hskip 14.226378 pt=2\left\langle\mathbf{g}_{n},\mathbf{x}_{n}-\tilde{\mathbf{x}}_{n+1} \right\rangle+\|\mathbf{A}(\mathbf{x}_{n}-\tilde{\mathbf{x}}_{n+1})\|_{2}^{2}\end{array}  \tag{5}\]It is clear that \(\tilde{x}_{n+1}\) is a better approximation to \(x_{n}+\alpha_{n}g_{n}\) than \(x_{n}\) is, so \(\left\|{\mathbf{x}_{n}+\alpha_{n}g_{n}-\tilde{x}_{n+1}}\right\|_{2}^{2}\leq\left\|{ \alpha_{n}g_{n}}\right\|_{2}^{2}\). By expanding the squares, we can obtain \(\left\|{\mathbf{x}_{n}-\tilde{x}_{n+1}}\right\|_{2}^{2}+2\alpha_{n}\left({\mathbf{x}_{ n}-\tilde{x}_{n+1}},{\mathbf{g}_{n}}\right)\leq 0\), substituting this into (5), one has  
\[\left\|{\mathbf{y}-  
the curve in Figure 4, where we discriminated between successful reconstructions (mostly occurring for \(1<s\leq 40\)) and unsuccessful reconstructions (mostly occurring for \(40<s\leq 80\)). As can be seen from Figure 4, in the successful case, the CGHTP algorithm requires fewer iterations than the CGIHT algorithm and HTP algorithm with \(\alpha^{*}\)(in the case \(\alpha^{*}=3.5\)). In the unsuccessful case, the number of iterations of CGHTP algorithm is comparable to that of HTP algorithm with \(\alpha^{*}\). This is because for the same measurement matrix \(\Phi\), when the sparsity level is small, the space formed by the columns of the \(\mathbf{A}_{T_{n}}\) is less correlated, so the condition number of \(\mathbf{A}_{T_{n}}^{\mathsf{T}}\mathbf{A}_{T_{n}}\) is small, the advantage of using CG method is obvious; as the sparsity level increase, the condition number of \(\mathbf{A}_{T_{n}}^{\mathsf{T}}\mathbf{A}_{T_{n}}\) becomes larger, which has a bad influence on the convergence rate of CGHTP. The average time consumed by different algorithms is shown in Figure 5. It can be seen that CGHTP algorithm requires the least average reconstruction time than other algorithms, because it requires fewer iterations than other algorithms.