# Conjugate Gradient Hard Thresholding Pursuit Algorithm for Sparse Signal Recovery  
[PERSON]  
1 Provincial Laboratory of Computer Integrated Manufacturing, Guangdong University of Technology, Guangzhou 510006, China; [EMAIL_ADDRESS] (Y.Z. ); [EMAIL_ADDRESS] (Y.H. ); [EMAIL_ADDRESS] (P.L. ); [EMAIL_ADDRESS] (X.F.) [PERSON]  
1 Provincial Laboratory of Computer Integrated Manufacturing, Guangdong University of Technology, Guangzhou 510006, China; [EMAIL_ADDRESS] (Y.Z. ); [EMAIL_ADDRESS] (Y.H. ); [EMAIL_ADDRESS] (P.L. ); [EMAIL_ADDRESS] (X.F.) [PERSON]  
1 Provincial Laboratory of Computer Integrated Manufacturing, Guangdong University of Technology, Guangzhou 510006, China; [EMAIL_ADDRESS] (Y.Z. ); [EMAIL_ADDRESS] (Y.H. ); [EMAIL_ADDRESS] (P.L. ); [EMAIL_ADDRESS] (X.F.) [PERSON]  
1 Provincial Laboratory  
Assume that a signal \(\mathbf{f}\in\mathbb{R}^{N}\) is \(s\)-sparse in some domain \(\mathbf{\psi}\). This means \(\mathbf{f}=\mathbf{\psi}\mathbf{x}\), and \(\mathbf{x}\) has at most \(s(s\ll N)\) nonzero entries. This system can be measured by a sampling matrix \(\mathbf{\Phi}\in\mathbb{R}^{M\times N}(M<N)\): \(\mathbf{y}=\mathbf{\Phi}\mathbf{f}=\mathbf{\Phi}\mathbf{\psi}\mathbf{x}=\mathbf{A}\mathbf{x}\), where \(\mathbf{y}\) is called measurement vector, \(\mathbf{A}\) is the so-called measurement matrix. The CS model is shown in Figure 2. If \(\mathbf{\Phi}\) is incoherent with \(\mathbf{\psi}\), the coefficient vector \(\mathbf{x}\) can be reconstructed exactly from a few measurements by solving the undetermined linear system \(\mathbf{y}=\mathbf{A}\mathbf{x}\) with constraint \(\left\|\mathbf{x}\right\|_{0}\leq s\), i.e., solving the following \(\ell_{0}\) norm minimization problem:  
\[\min\left\|\mathbf{x}\right\|_{0}\quad s.t.\quad\mathbf{y}=\mathbf{A}\mathbf{x}. \tag{1}\]  
As a combinatorial optimization problem, the above \(\ell_{0}\) norm optimization is NP-hard [8]. One way to solve such problem is to transform it into a \(\ell_{1}\) norm optimization problem:  
\[\min\left\|\mathbf{x}\right\|_{1}\quad s.t.\quad\mathbf{y}=\mathbf{A}\mathbf{x}. \tag{2}\]  
Since \(\ell_{1}\) norm-based problem is convex, some methods such as basis pursuit (BP) [7] and LASSO [9] are usually employed to solve the \(\ell_{1}\) norm minimization in polynomial time. The solutions obtained by these algorithms can well approximate the exact solution of (1). However, their computational complexity is too highly impractical for many applications. As a relaxation of the \(\ell_{0}\) norm optimization, the \(\ell_{p}\) norm for CS reconstruction has attracted extensive research interest, and the problem can be formulated as the following optimization problem:  
\[\min\left\|\mathbf{x}\right\|_{p}\quad s.t.\quad\mathbf{y}=\mathbf{A}\mathbf{x}, \tag{3}\]  
where \(\left\|\mathbf{x}\right\|_{p}=\left(\sum\limits_{i=1}^{N}\left|x_{i}\right|^{p} \right)^{1/p}\) denotes the \(\ell_{p}\) norm of \(\mathbf{x}\). There are many methods have been developed to solve such problem [10; 11; 12; 13]. Many studies have shown that using \(\ell_{p}\) norm for \(0<p<1\) requires fewer measurements and has much better recovery performance than using \(\ell_{1}\) norm [14; 15]. However, \(\ell_{p}\) norm leads to a non-convex optimization problem which is difficult to solve efficiently. Sparse signals can be quickly recovered by these algorithms while the measurement matrix satisfying the so-called restricted isometry property (RIP) with a constant parameter. A measurement matrix is said to satisfy the \(s\)-order RIP if for any \(s\)-sparse signal \(\mathbf{x}\in\mathbb{R}^{N}\)  
\[(1-\delta_{s})\leq\left\|\mathbf{A}\mathbf{x}\right\|_{2}^{2}\Big{/}\left\|\mathbf{x} \right\|_{2}^{2}\leq(1+\delta_{s}), \tag{4}\]  
where \(0\leq\delta_{s}\leq 1\). Commonly used sampling matrices include Gaussian matrices, random Bernoulli matrices, partial orthogonal matrices, etc. The measurement matrices consisting of these sampling matrices and orthogonal basis usually satisfy the RIP condition with a high probability [16].