## 3 Compressive Sensing Based Preamble Channel Estimation
### Adaptive Regularized Compressive Sampling Matching Pursuit Algorithm
#### 3.3.2 Proposed Algorithm  
CoSaMP algorithm can reconstruct source signals with high efficiency. However, the algorithm requires the prior knowledge of sparsity. SAMP algorithm provides a way for blind sparse reconstruction. Motivated by the advantages in the two greedy algorithms and associated with a regularized process, we propose a new greedy algorithm, named sparse adaptive regularized compressive sampling matching pursuit (ARCoSaMP).  
The proposed algorithm can automatically adjust the selected atoms to reconstruct the unknown sparsity signal in the iterative process. A similar backtracking theory of CoSaMP is utilized to reconstruct partial information of the target signal in the iterative process. An iterative process is divided into multiple stages, the proposed algorithm adaptively estimates the sparsity with steps through stage by stage and set it to the length of the initial support, then gets the accurate target signal by regularization screening of atoms in every stage. The algorithm basic steps are shown below:  
**Input**: measurement matrix \(\Phi\), the measurement vector \(y\), the initial step size \(s\)  
**Output**: a \(K\)-sparse approximation \(\hat{h}\) of the channel \(h\)  
1. Initialization: residual \(r=y\), iterative \(it=1\), initial step \(s=1\), \(stage=1\), index value set \(I=\phi\), \(J=\phi\).
2. Set a threshold value \(\varepsilon\), if the reconstruction \(\hat{h}\) satisfies \(\parallel h-\hat{h}\parallel_{2}\leq\varepsilon\), and stop the iteration; otherwise, continue to Step 3. The deviation norm 2 is chosen as the basis of the iterative termination. In the simulation, \(\varepsilon=10^{-7}\).
3. Calculate the correlation coefficient \(u\) by the Equation (13), which calculates the absolute value of inner product between residual \(r\) and each atom of measurement matrix \(\Phi\), and deposit the index values corresponding the 2s maximum values from \(u\) to \(J\): \[u=\left\{u_{j}\left|u_{j}=\left|\left\langle r,\Phi_{j}\right\rangle\right| \right.,j=1,2,\cdots,N\right\}\] (13)
4. Regularization: using Equation (14) to regularize \[\left|u(i)\right|\leq 2\left|u(j)\right|\text{ for all }i,j\in J_{0}\] (14) choose \(J_{0}\) with the maximal energy \(\parallel\left.u\right|_{J_{0}}\parallel_{2}\), add the set \(J_{0}\) to the index set \(I\), and update the support set \(\Phi_{I}\).
5. Use Equation (15) to get \(\hat{h}\), according to the backtracking mechanism, take atoms corresponded to the largest \(s\) elements of \(\hat{h}\) to \(I\), update the support set \(\Phi_{I}\): \[\hat{h}=\text{argmin}\parallel y-\Phi_{I}h\parallel_{2}\] (15)
6. Update the residual \[r_{new}=y-\Phi_{I}\hat{h}\] (16)
7. Make a comparison between the update residual and the last iteration residual; if \(\parallel r_{new}\parallel_{2}\geq\parallel r_{n-1}\parallel_{2}\), \(stage=stage+1\), \(s=s\cdot stage\), return to Step 3; otherwise, \(r=r_{new}\), \(n=n+1\), and return to Step 2.  
The selection of the initial step is very important, and if the step size is too large, there may an overestimating problem. In the proposed algorithm, the initial step size is 1, which is less than the reality of the sparsity \(K\) until the final stage. Iteration loop follows the CoSaMP and regularization to identify support sets in the target signal. When \(s<K\), it is necessary to take an effective mechanism for stage switching. In the proposed algorithm, we trigger the stage switching between two consecutive iterations when the relevant residual improvement begins to disappear.