## 3 OTFS Channel Estimation
### Latency/Complexity Comparison  
The key advantage of the proposed approach is that it requires a single final refinement procedure compared to the \(\hat{P}-1\) refinements performed by the DDIPIC algorithm. A rough latency comparison of the two approaches is shown in Table 1, where we assumed that the P-IPIC algorithm does not overestimate the number of paths significantly during the first iterative procedure; thus, \(\hat{P}\approx\hat{P}\). Under this hypothesis, and denoting by \(T_{\text{coarse}}\) the average time needed to perform a coarse estimate and with \(T_{\text{fine}}\) the average time needed to perform a fine estimate, we can make the following observations. 1. DDIPIC: This performs a coarse and fine estimation for every path in a time equal to \(\hat{P}(T_{\text{coarse}}+T_{\text{fine}})\). Moreover, from the second iteration to the end, it performs \(\hat{P}-1\) refinement procedures of the estimates. Therefore, at each refinement procedure, it performs \(i\) coarse and fine estimates. 2. P-IPIC: This performs a coarse and fine estimation for every path in a time equal to \(\hat{P}(T_{\text{coarse}}+T_{\text{fine}})\) during the _search phase_. Moreover, the _refinement phase_ performs a second coarse and fine estimate for each path. During the _search phase_, the proposed P-IPIC algorithm runs coarse and fine estimation procedures of channel delays and Dopplers performing maximization of the cost function in Equation (21), while during the _refinement phase_, it maximizes the regularized version of Equation (19). The complexity comparison of the cost function in Equation (19) and the RCF is shown in Table 2. It can be noticed that the first advantage in computing the RCF is that it does not require matrix inversion but only multiplications and additions; instead, the computation of the cost function in Equation (19) does. In order to compare the two cost functions, we can make the following observations. 1. DDIPIC cost function in (19): During the \(i\)-th iteration, the number of required operations is \begin{table}
\begin{tabular}{l c} \hline \hline
**Algorithm** & **Latency** \\ \hline DDIPIC [11] & \((T_{\text{coarse}}+T_{\text{fine}})\hat{P}+(T_{\text{coarse}}+T_{\text{fine}}) \sum_{i=2}^{\hat{P}}i=\) \\  & \(2(T_{\text{coarse}}+T_{\text{fine}})\hat{P}+(T_{\text{coarse}}+T_{\text{fine}}) \Big{(}\frac{\hat{P}(\hat{P}-1)}{2}-1\Big{)}\) \\ \hline P-IPIC (Prop.) & \(2(T_{\text{coarse}}+T_{\text{fine}})\hat{P}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Latency comparison of the two IPIC algorithms. \(\mathbf{y}^{H}\mathbf{R}\big{(}\boldsymbol{\tau},\boldsymbol{\
u}\big{)}\), \(\mathbf{y}\in\mathbb{C}^{MN\times 1}\), \(\mathbf{R}\big{(}\boldsymbol{\tau},\boldsymbol{\
u}\big{)}\in\mathbb{C}^{MN\times i}\) requires \(MNi\) multiplications and \((MN-1)i\) additions. Then, \(\mathbf{R}^{H}\big{(}\boldsymbol{\tau},\boldsymbol{\
u}\big{)}\mathbf{y}\) is simply obtained applying the Hermitian operator. \(\mathbf{R}^{H}\big{(}\boldsymbol{\tau},\boldsymbol{\
u}\big{)}\mathbf{R} \big{(}\boldsymbol{\tau},\boldsymbol{\
u}\big{)}\in\mathbb{C}^{i\times i}\) requires \(MNi^{2}\) multiplications and \((MN-1)i^{2}\) additions. After that, matrix inversion has a complexity in the order of \(\mathcal{O}(i^{3})\). \(\mathbf{y}^{H}\mathbf{R}\big{(}\boldsymbol{\tau},\boldsymbol{\
u}\big{)} \Big{(}\mathbf{R}^{H}\big{(}\boldsymbol{\tau},\boldsymbol{\
u}\big{)}\mathbf{ R}\big{(}\boldsymbol{\tau},\boldsymbol{\
u}\big{)}\Big{)}^{-1}\) requires \(i^{2}\) multiplications and \(i(i-1)\) additions. \(\mathbf{(d)}\) The matrix multiplication of the \(1\times i\) matrix obtained in the previous step by \(\Big{(}\mathbf{y}^{H}\mathbf{R}\big{(}\boldsymbol{\tau},\boldsymbol{\
u} \big{)}\Big{)}^{H}\) requires \(i\) multiplications and \(i-1\) additions. 2.