# 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  
Knowing that the observation matrix of \(M\times N\) is \(\Phi\), that the observation vector is \(y\), and that the sparsity is \(K\), the steps to solve the sparse signal \(\hat{s}\) using the OMP algorithm are as follows:  
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 a number of iterations of \(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}\bigl{|}\bigl{<}r_{t-1},\alpha_{j}\bigr{>} \bigr{|}\] (24) where \(\alpha_{j}\) denotes the \(j\)th column of observation matrix. 3. The index set \(\Lambda_{t}=\Lambda_{t-1}\cup\ \{\lambda_{t}\}\) is updated, and \(A_{t}=A_{t-1}\cup\alpha_{\lambda_{t}}\); where \(t\) denotes the current number of iterations and the number of elements in the current index set. 4. The least square solution is found: \[\hat{s}_{t}=\arg\min_{s}\lVert y-A_{t}s_{t}\rVert=\left(A_{t}^{H}A_{t}\right)^ {-1}A_{t}^{H}y\] (25)
5. New approximations and residuals are calculated: \(r_{t}=y-A_{t}\hat{s}_{t}\). 6. If \(t<K\), the process returns to step 2; otherwise, iteration is stopped and returns to step 7. 7. The non-zero element position set of \(\hat{s}\) obtained from the reconstruction is \(\Lambda_{t}\), and the value of the non-zero element is the solution of the last iteration \(\hat{s}_{t}\). The OMP algorithm guarantees the optimality of each iteration, with the number of iterations equal to the sparsity value. The main ideas of the SOMP and OMP algorithms are the same, and their difference lies only in step 2. When searching for the column index of the observation matrix that most matches the residual, corresponding to a number of joint sparse signals, the inner products of the residual and the column are summed, and then the column corresponding to the maximum value is selected. The other steps are exactly the same. All solutions of sparse signals are obtained via the LS rule. It should be noted that, when the OMP algorithm is applied to reconstruct the original signal, the observation matrix \(\Phi\) is known. According to Equation (14), \(\Phi_{i}\) is the matrix of \(M\times(L+1)\), where \(L\) is channel length, which is related to the maximum delay spread of the channel. However, in practical applications, \(L\) is unknown and can only be obtained by estimating the realistic maximum delay of the channel, which is usually greater than the actual channel length. Reference [22] proposed a PIA-OMP algorithm based on a priori information, which improved OMP reconstruction accuracy and, thus, channel estimation performance. By inserting the cyclic prefix of the first TS as a guard Interval in the header of a transmitted frame, this method obtains a priori information such as the channel length and sparsity, but it sacrifices some spectral efficiency. In addition, it assumes a constant CIR within a frame, which has limitations for application in fast-fading channels. In this research, we propose an improved scheme that can be applied to both the OMP and SOMP algorithms. It can significantly improve the performance of the reconstruction algorithm without sacrificing spectral efficiency. Based on the maximum possible delay, the channel length is preset to be \(L\), and a more precise channel length is calculated when the path delay set is obtained through several iterations. The set is estimated to be \(\hat{\Omega}_{i}=\{\hat{\tau}_{0},\hat{\tau}_{1},\cdots\hat{\tau}_{K-1}\}\); then, the channel length is \(L=\hat{\tau}_{K-1}\) and \(\hat{L}\leq L\). Therefore, the length of the IBI-free region \(M\) is enhanced, and thus, the observation matrix is updated as follows:  
\[\Phi^{\prime}_{i}=