## 3 Robust Low-Complexity CFO Estimator
### Proposed Search-Based CFO Estimator  
Let \(\mathbf{Q}\) denote the \(N\times K\) interpolation matrix. The linear interpolation is widely used, and for the considered system, the \(N\times K\) matrix \(\mathbf{Q}\) is given by:  
\[\mathbf{Q}=\left[\begin{array}{ccccc}\mathbf{q}_{1}&\mathbf{q}_{2}&&&\\ &\mathbf{q}_{1}&\mathbf{q}_{2}&&&\\ &&\ddots&\ddots&\\ &&&\mathbf{q}_{1}&\mathbf{q}_{2}\\ &&&\mathbf{q}_{1}\end{array}\right] \tag{10}\]where:  
\[\begin{array}{l}\mathbf{q}_{1}=\frac{1}{N}\times\left[N,N-K,N-2K,\cdots,2K,K \right]^{T}\\ \mathbf{q}_{2}=\frac{1}{N}\times\left[0,K,2K,\cdots,N-2K,N-K\right]^{T}\end{array} \tag{11}\]  
The full-dimensional CFR can be derived from Equation (3) and written by the expression:  
\[\begin{array}{l}\hat{\mathbf{H}}(\epsilon)=\mathbf{Q}\hat{\mathbf{H}}_{P}( \epsilon)\\ \phantom{\hat{\mathbf{H}}(\epsilon)}=\mathbf{Q}\mathbf{D}_{\mathbf{X}_{P}}^{-1 }\mathbf{S}\hat{\mathbf{R}}(\epsilon)\end{array} \tag{12}\]  
Applying \(N\)-point IFFT to \(\hat{\mathbf{h}}\), the full-dimensional time-domain channel response reaches:  
\[\begin{array}{l}\hat{\mathbf{h}}(\epsilon)=\mathbf{F}^{H}\hat{\mathbf{H}}( \epsilon)\\ \phantom{\hat{\mathbf{H}}(\epsilon)}=\mathbf{F}^{H}\mathbf{Q}\mathbf{D}_{ \mathbf{X}_{P}}^{-1}\mathbf{S}\hat{\mathbf{R}}(\epsilon).\end{array} \tag{13}\]  
Summing up the energy of the last \(N-N_{g}\) entries of \(\hat{\mathbf{h}}(\epsilon)\) in Equation (13), the CRE is given by:  
\[\begin{array}{l}f(\epsilon)=\sum_{j=N_{g}+1}^{N}\left|\left[\hat{\mathbf{h} }(\epsilon)\right]_{j}\right|^{2}\\ \phantom{\hat{\mathbf{H}}(\epsilon)}=\left\|\tilde{\mathbf{J}}\mathbf{F}^{H} \mathbf{Q}\mathbf{D}_{\mathbf{X}_{P}}^{-1}\mathbf{S}\mathbf{F}\mathbf{D}_{ \mathbf{a}(\epsilon)}^{H}\right\|^{2}\\ \phantom{\hat{\mathbf{H}}(\epsilon)}=\mathbf{a}^{T}(\epsilon)\mathbf{D}_{ \mathbf{r}}^{H}\mathbf{F}^{H}\mathbf{S}^{T}\mathbf{D}_{\mathbf{X}_{P}}^{-1} \mathbf{Q}^{H}\mathbf{F}\tilde{\mathbf{J}}^{T}\tilde{\mathbf{J}}\mathbf{F}^{H} \mathbf{Q}\mathbf{D}_{\mathbf{X}_{P}}^{-1}\mathbf{S}\mathbf{F}\mathbf{D}_{ \mathbf{r}}^{T}\mathbf{a}^{*}(\epsilon)\\ \phantom{\hat{\mathbf{H}}(\epsilon)}=\mathbf{a}^{H}(\epsilon)\mathbf{D}_{ \mathbf{r}}\mathbf{T}^{*}\mathbf{D}_{\mathbf{r}}^{H}\mathbf{a}(\epsilon)\end{array} \tag{14}\]  
where:  
\[\begin{array}{l}\tilde{\mathbf{J}}=\left[\mathbf{O}_{(N-N_{g})\times N_{g}}, \mathbf{I}_{N-N_{g}}\right]\\ \mathbf{T}=\mathbf{F}^{H}\mathbf{S}^{T}\mathbf{D}_{\mathbf{X}_{P}}^{-1} \mathbf{Q}^{H}\mathbf{F}\tilde{\mathbf{J}}^{T}\tilde{\mathbf{J}}\mathbf{F}^{H }\mathbf{Q}\mathbf{D}_{\mathbf{X}_{P}}^{-1}\mathbf{S}\mathbf{F}\\ \mathbf{r}=\mathbf{F}^{H}\mathbf{R}\\ \mathbf{D}_{\mathbf{X}_{P}}^{H}=\mathbf{D}_{\mathbf{X}_{P}}^{-1}\end{array} \tag{15}\]  
Note that the last equation in Equation (14) holds since the CRE is a positive real number. Clearly, the value of the expression Equation (14) achieves a minimum value when \(\epsilon=\epsilon_{d}\). Thus, the CFO estimate can be determined in accordance with the criterion shown below:  
\[\begin{array}{l}\hat{\epsilon}_{d}=\arg\min_{\epsilon}\ \ f(\epsilon)\\ \phantom{\hat{\mathbf{H}}(\epsilon)}\equiv\arg\min_{\epsilon}\ \ \mathbf{a}^{H}( \epsilon)\mathbf{D}_{\mathbf{r}}\mathbf{T}^{*}\mathbf{D}_{\mathbf{r}}^{H} \mathbf{a}(\epsilon)\end{array} \tag{16}\]  
From Equation (16), the choice of the granularity, \(\Delta_{\epsilon}\), involves the tradeoff between the estimator's performance and computational complexity. That is, decreasing \(\Delta_{\epsilon}\) can improve the estimator's performance at the expense of additional computational complexity, which is proportional to \(\Delta_{\epsilon}^{-1}+1\).