# An Improved Orthogonal Matching Pursuit Algorithm for CS-Based Channel Estimation
## 2 Materials and Methods
### Improvement of the OMP Algorithm
#### 2.2.2 Improvement of the OMP Algorithm
\begin{bmatrix}c_{i,\hat{L}}&c_{i,\hat{L}-1}&c_{i,\hat{L}-2} &\cdots&c_{i,0}\\ c_{i,\hat{L}+1}&c_{i,\hat{L}}&c_{i,\hat{L}-1}&\cdots&c_{i,1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ c_{i,p-1}&c_{i,p-2}&c_{i,p-3}&\cdots&c_{i,p-L-1}\end{bmatrix} _{M^{\prime} \times(L+1)} \tag{26}\]where \(M^{\prime}=P-\hat{L}\), and \(M^{\prime}>M\). The number of rows of \(\Phi^{\prime}_{i}\) is increased, and the number of columns is decreased compared to the initialized observation matrix given in Equation (14). Substituting Equation (26) into Equation (13) yields the following:  
\[R_{i}^{\prime}=\Phi^{\prime}_{i}H^{\prime}_{i}+V^{\prime}_{i} \tag{27}\]  
where \(R_{i}^{\prime}\) is the IBI-free region signal with length \(M^{\prime}\), which is the observation vector in the OMP algorithm and is recorded as \(R^{\prime}_{i}=[d_{i,\hat{L}^{\prime}},d_{i,\hat{L}+1^{\prime}},\ldots,d_{i,P-1 }]^{T}\),\(H^{\prime}_{i}=[h_{i,0},h_{i,1},\ldots,h_{i,\hat{L}}]^{T}\), and \(V^{\prime}_{i}\) is the vector that contains the last \(M^{\prime}\) samples of the additive Gaussian white noise signal \(N_{i}\). According to Equation (23), and due to the increase of \(M\), the CRLB is decreased, and according to Equation (27), the recalculation of the channel path gain based on the LS criterion provides a certain performance gain. Based on the new vector \(R_{i}^{\prime}\) and the observation matrix \(\[PERSON]^{\prime}_{i}\), as well as the estimated path delay set \(\hat{\Omega}_{i}\), the overdetermined equation \(R^{\prime}_{i}=\[PERSON]^{\prime}_{i}|_{\hat{\Omega}_{i}}H^{\prime}_{i}\) is solved, where \(\[PERSON]^{\prime}_{i}|_{\hat{\Omega}_{i}}\) is the column set of \(\[PERSON]^{\prime}_{i}\) with the column index in the set \(\hat{\Omega}_{i}\), which can be obtained according to the least squares criterion:  
\[\hat{H}_{i}=\left(\[PERSON]^{\prime}_{i}|_{\hat{\Omega}_{i}}H^{\prime} \[PERSON]^{\prime}_{i}|_{\hat{\Omega}_{i}}\right)^{-1}\[PERSON]^{\prime}_{i}|_{\hat{ \Omega}_{i}}H^{\prime}_{i} \tag{28}\]  
In summary, Figure 3 shows the process of the proposed scheme for the OMP and SOMP algorithms. The modules of the conventional OMP and SOMP algorithms are outside the dashed box, and the improvement parts are inside it. Compared with conventional algorithms, better estimation performance is obtained by employing the proposed scheme. Since both methods fully utilize the IBI-free region signal as an observation vector, the proposed method in this research is able to achieve the same performance gains as the method in reference [22], but it does not require additional pilots. Furthermore, since matching pursuit algorithms are all based on obtaining accurate path delay estimates before calculating the path gain, the proposed method is also applicable to other matching pursuit algorithms. Algorithm 1 summarizes the steps of the proposed improved OMP algorithm. The initial observation matrix \(\Phi\) is \(\Phi_{i}\) in Equation (14) with a size of \(M\times(L+1)\), the observation vector \(y\) is \(R_{i}\) in Equation (13), the sparse signal \(s\) is \(H_{i}\), the sparsity level is \(K\), and the updated observation matrix is \(\Phi^{\prime}_{i}\) in Equation (26). Figure 3: The process of the improved OMP algorithm. ```
1. Initialization parameters : residual \(r_{0}=y\), index set \(\Lambda_{0}=\varnothing\), the set of selected column vectors in the observation matrix \(A_{0}=\varnothing\), and number of iterations \(t=0\). 2. \(t=t+1\), a column \(\alpha_{j}\) of the observation matrix \(\Phi\), is searched for the elements that best match the residual according to the principle of maximum correlation, and the index set \(\lambda_{t}\) is updated, which satisfies the following: \[\lambda_{t}=\arg\max_{j=1,2,3,...,N}\left|\left<r_{t-1},\alpha_{j}\right>\right|\]
3. The index set \(\Lambda_{t}=\Lambda_{t-1}\cup\left\{\lambda_{t}\right\}\) and the set of selected column vectors \(A_{t}=A_{t-1}\cup\alpha_{\lambda_{t}}\) are updated, where \(t\) denotes the current number of iterations and the number of elements in the current index set. 4.