Low Time Complexity Near-Field Channel and Position Estimations

In order to find better near-field channel estimation methods, we will analyze the physical meaning of near-field channel parameters in this section. According to equation (4), the UE’s location information is contained in $\phi(x)$. According to equations (5) and (7), we can obtain:

where

and

We can observe that the distance and angle information of the user are coupled in $p_{1}$, while the information of $p_{1}$ and $p_{2}$ are coupled in $\phi$. Therefore, if the distance and angle of the user are estimated directly on $\phi$, there will be a phenomenon of mutual coupling between parameters.

We address the parameter coupling phenomenon in near-field channels from two aspects. Firstly, we directly estimate $p_{1}$ and $p_{2}$, and then estimate the UE’s position using equations (9) and (10) after obtaining $p_{1}$ and $p_{2}$. Secondly, we will find a method to decouple $p_{1}$ and $p_{2}$ based on their physical meanings. We use $\beta(x)$ to represent the direction in which the antenna at position $(x,0,0)$ looks towards the UE, that is:

where $\theta_{x}$ is the elevation angle of the antenna at position $(x,0,0)$ towards the UE. According to equation (8), the following holds:

Since $\beta(0)=p_{2}$, $p_{2}$ represents the channel direction at the reference antenna. We define the channel direction at the reference antenna as the angel of arrival (AoA) and the rate of change of a channel with respect to space as the curvature of arrival (CoA) of the channel, which is:

From equation (13), it can be seen that the physical meaning of $p_{1}$ is the curvature of the channel. Fig. 2 shows the relationship between $p_{1}$ and $p_{2}$ and UE’s location. It can be seen that the size of $p_{1}$ affects the CoA of the wavefront, regardless of its direction while $p_{2}$ represents the direction of the tangent plane of the wavefront at the reference antenna, without affecting the curvature of the wavefront. Therefore, as long as we find a method that can estimate channel CoA and AoA separately, we can decouple $p_{1}$ and $p_{2}$.

In this section, we explore the dual relationship between the near-field problem and the Doppler problem to find a method for estimating the near-field channel CoA, and then use the estimated CoA information to estimate the AoA.

For the time-domain function ${h}(t)=e^{\jmath\phi(t)}$, if $\phi^{\prime}(t)$ is a constant value, then ${h}(t)$ is stationary, and its frequency spectrum ${H}(\omega)$ does not change with time. If there is Doppler effect in the channel, ${h}(t)$ becomes non-stationary. At this point, $\phi^{\prime}(t)$ is not a constant value, and ${H}(\omega)$ also changes with time. The coherence time of ${h}(t)$ can reflect the speed at which ${H}(\omega)$ changes over time.

In near-field problems, the channel also exhibits properties similar to the Doppler effect. We use $\kappa=\frac{k_{x}}{k}$ to represent the direction of the channel, where $k_{x}$ is the projection of $k$ in the $x$-axis direction. We select a small interval $(x_{0},x_{0}+\Delta x)$ on the array, where $\phi(x)$ can be seen as a linear function. The pattern on this interval can be written as:

When $\beta(x)$ is a constant independent of $x$, $H(\kappa)$ does not change with the variation of $x$, and at this time $h(x)$ is spatially stationary. When $\beta(x)$ is not a constant, $h(x)$ is spatially non-stationary.

We can compare the time signal and spatial signal and find that the Doppler effect causes $h(t)$ to be non-stationary in time, and the near-field effect causes $h(x)$ to be non-stationary in space. Therefore, we call the near-field effect the spatial Doppler effect. Hence, we can imitate the time-domain Doppler estimation method and propose its dual spatial Doppler estimation method. Thus, we proposed the concept of coherent space by imitating the concept of coherent time. According to equation (6), when the distance from the user to the reference antenna is greater than the Rayleigh distance, the channel model can be considered as a far-field model. At this point, $p_{1}=0$ and $\beta(x)=p_{2}$ is a constant, so the signal is spatial stationary, meaning that the signal is coherent in the space of the array. Therefore, we define coherent space as the range where the channel can be viewed as a far-field on the line of the array. We use $\chi_{0}$ to represent the length of the coherent space. As shown in Fig. 3, the coherence space size of the channel varies for users at different locations. For user 3, its distance from the reference antenna is equal to the Rayleigh distance, therefore $\chi_{0}^{{\rm user}3}=D$, where $D$ is the physical size of the array. For user 4, it is located in the far-field region of the array, therefore $\chi_{0}^{{\rm user}4}>D$. The electromagnetic waves emitted by user 4 can be regarded as plane waves on the array. For near-field users, such as user 1 and user 2, the coherence space of their channels is smaller than the array size, so the channels cannot be considered spatially coherent, i.e. plane wave models cannot be used. And because user 1 is closer to the array than user 2, $\chi_{0}^{{\rm user}1}<\chi_{0}^{{\rm user}2}$.

Therefore, we found that by measuring the spatial coherence of the signals received by the array, we can determine the distance from the user to the reference antenna. If the signals on the entire array are coherent, it indicates that the user is in the far field, while if only a portion is coherent, it indicates that the user is in the near field of the array. The smaller the coherence space, the greater the rate of change of channel direction with space, that is, the larger the CoA. So we can solve $p_{1}$ by doing autocorrelation on the signal. In the next subsection, we will provide a detailed introduction to the functional relationship between signal autocorrelation and $p_{1}$.

We define the amplitude spectrum of the spatial autocorrelation function of the received signal as:

where $\chi$ represents the displacement in the autocorrelation function. According to equation (15), we can write the solution of $p_{1}$ as:

After estimating the parameter $p_{1}$, we can construct a new signal form to transform the near-field problem into a far-field problem:

At this point, $\widetilde{h}(x)$ is equivalent to a far-field channel, so we can use traditional far-field channel estimation methods to estimate parameter $p_{2}$. Finally, based on equation (7), we can obtain the estimated channel $\hat{h}$, and based on equations (9) and (10), we can obtain $\hat{\theta}$ and $\hat{r}$.

In summary, we decompose the near-field estimation process into two steps: estimating $p_{1}$ and $p_{2}$. The process of estimating $p_{1}$ is an estimation method similar to the Doppler effect, which uses autocorrelation function for estimation. The process of estimating $p_{2}$ is essentially an estimation of the directional pattern, which is to determine which direction the signal has the greatest cross-correlation with. Therefore, the estimation model proposed in this paper is named the joint auto-correlation and cross-correlation (JAC) scheme.

In this part, we use the inverse function of the sinc function to solve the parameter $p_{1}$, so we call this algorithm the JAC-ISF algorithm.

According to equation (15), the analytical solution of $p_{1}$ can be expressed as the inverse function of the $sinc$ function. However, the $sinc$ function is not a monotonic function and does not have an inverse function. Therefore, we need to truncate the $sinc$ function and use its monotonic interval for channel estimation. Firstly, we can discard the sidelobes and only retain the main lobe. This is because near-field scenes are often accompanied by the presence of XL-MIMO. In XL-MIMO scenario, the sidelobe amplitude of the $sinc$ function is much lower than that of the main lobe, so the anti noise performance of the sidelobes is worse. Secondly, according to equation (9), we know that $p_{1}$ must be a negative value. Therefore, we only need to retain the part of the $sinc$ function $(-1,0)$. On this interval, the $sinc$ function is a monotonically increasing function and therefore has an inverse function. Thus, ${\rm arc}sinc(x)$ can be written as:

Fig. 4 shows the graph of the ${\rm arc}sinc$ function.

Since we need to compare the autocorrelation function with the $sinc$ function to obtain the value of $p_{1}$, the autocorrelation function also needs to capture points within the main lobe. According to equation (15), the estimated value of the autocorrelation function can be written as:

where $\xi\in\mathbb{Z}$ and $\eta$ are the number of points in the autocorrelation function and the number of shifts when performing autocorrelation functions. We can see that when the value of $\xi$ is small, the estimated value of the autocorrelation function is more accurate. However, the number of points in the autocorrelation function decreases, resulting in insufficient data for estimating $p_{1}$. On the contrary, if the value of $\xi$ is large, it will lead to inaccurate estimation of the autocorrelation function. In practical applications, if there is prior information, the appropriate $\xi$ should be selected based on the prior information. In order to consider a more general situation, we choose $\xi=\lfloor\frac{N}{2}\rfloor$. Then, we need to determine whether the autocorrelation function has zero points to determine if all data is within the main lobe. Due to the fact that autocorrelation functions may not necessarily have zero points when $\eta$ is an integer, we cannot extract data within the main lobe by finding $\eta$ values that satisfy $c[\eta]=0$. Therefore, we select a small value¹¹1Here we have chosen $\delta=0.1$ based on experience. In fact, the choice of $\delta$ does not have a significant impact on the performance of the algorithm, so it is sufficient to choose the appropriate one when applying this algorithm. $\delta=0.1$ and use $\Upsilon$ to represent the set of $\eta$ that satisfies $c[\eta]\leq\delta$, that is:

Thus, the number of points retained for the autocorrelation function is:

Substituting $\chi=\eta d$, according to equations (15) and (16), the estimated value of $p_{1}$ is:

According to equation (17), we use the estimated $p_{1}$ to construct an equivalent far-field signal:

Then we use the MUltiple SIgnal Classificatio (MUSIC) algorithm on $\widetilde{\bm{Y}}$ to estimate the direction of the maximum eigenvalue, which is $p_{2}$. Finally, the estimated channel is:

Since this algorithm obtains $p_{1}$ by inverting the $sinc$ function, we refer to it as the Inverse Sinc Function (ISF) algorithm. The details of this algorithm are summarized in Algorithm 1.

In this subsection, we use gradient descent to solve the parameter $p_{1}$. Therefore, we call this algorithm the JAC-GD algorithm.

Similar to the JAC-ISF algorithm, we obtain an estimate of the autocorrelation function using equation (19). According to equation (16), we set the loss function as:

The gradient of the Loss function is:

We update $p_{1}$ based on the learning rate $\alpha$, that is:

where $n_{\rm itr}$ is the index of the number of iterations. We adopt the learning rate of inverse time decay, that is:

where $\alpha_{0}$ is the initial learning rate and $\gamma$ is the decay factor. The details of this algorithm are summarized in Algorithm 2.

We define the unknown parameter vector as:

The probability density function of the received signal is:

where ${\bm{R}=\sigma^{2}{\bm{I}}_{NL}}$ and

We define $\mathbb{E}\{(\hat{\bm{\epsilon}}_{1}-{\bm{\epsilon}}_{1})(\hat{\bm{\epsilon}}_{1}-{\bm{\epsilon}}_{1})^{\rm T}\}$ as the covariance matrix of the unknown parameter vector $\bm{\epsilon}$, where $\hat{\bm{\epsilon}}$ is the unbiased estimator of $\bm{\epsilon}$. The covariance matrix has the following inequality relationship:

where the $\rm CRLB$ is cramer-rao lower bound (CRLB) and satisfies:

The Fisher information matrix ${\rm FIM}^{-1}({\bm{\epsilon}}_{1})$ can be obtained by the Slepian-Bangs equation [30], which is shown in (34):

When $T$ is large, the dimensionality of the FIMs also becomes large, making the inverse operation more difficult. Therefore, we solve ${\rm FIM}^{-1}$ by solving the Schur complement of the matrix. After simplification, we can obtain the CRLB of unknown parameters $p_{1}$ and $p_{2}$:

where $f(x)=\sum_{n=1}^{N}(nd)^{x}$.

For the localization problem, we want to know the CRLB of $\theta$ and $r$, so we define the parameter vector $\bm{\epsilon}_{2}$ as:

We exploit the theory of parameter transformation for CRLB of $\bm{\epsilon}$ [31]:

By combining equations (9) and (10), we can obtain the CRLB of $\theta$ and $r$ as follows:

and (40).

According to equation (40), we can see that the larger $r$, the higher the $\rm CRLB$, and when $r\rightarrow\infty$, the ${\rm CRLB}(r)\rightarrow\infty$. This is consistent with the conclusion that the array cannot determine the distance from the user to the array in far-field situations.

The computational complexities of the proposed ISF algorithm is analyzed, which are summarized in Table I. For solving and the autocorrelation function, i.e. equation (19), the time complexity is $\mathcal{O}(TN)$. The time complexity of the process of extracting the autocorrelation function in equations (20) and (21) are $\mathcal{O}(N)$. The time complexity of using autocorrelation function to estimate $p_{1}$ in equation (22) is $\mathcal{O}(N_{\eta})$, but $sinc$ $N_{\eta}$ is proportional to $N$, the time complexity is $\mathcal{O}(N)$. In summary, the total time complexity of estimateing $p_{1}$ is $\mathcal{O}(TN)$. The process of estimating $p_{2}$ is the MUSIC algorithm, so the time complexity is $\mathcal{O}(TN)$. Finally, the total time complexity of the ISF algorithm is $\mathcal{O}(TN)$.

In the P-SOWP algorithm, $S$ refers to the number of grids divided by distance. Although [32] mentions that $S$ is not a large number compared to $N$. However, as $N$ increases, $S$ also increases synchronously. This is because when $N$ increases, the distance resolution of the array increases. In the time complexity of the P-SIGW algorithm, $N_{\rm iter}$ refers to the number of iterations of the algorithm.

Through the comparison of time complexity in Table I, we found that the time complexity of most near-field estimation algorithms is the time complexity of distance estimation multiplied by the time complexity of angle estimation [33]. This is because most algorithms use the principle of cross-correlation to estimate the near-field channel. The principle of cross-correlation refers to determining which space a user is in by examining the correlation between channels and different spaces. This type of channel estimation algorithm based on cross-correlation relies on orthogonal spatial decomposition. In near-field problems, it is difficult to divide the entire space into different orthogonal spaces due to the coupling of distance and direction variables. Moreover, due to the addition of distance as a dimension for measuring space, the time complexity of near-field algorithms exhibits multiplicative time complexity. The JAC model and ISF algorithm proposed in this paper decouple two parameters in near-field channel estimation, and make the time complexity of the entire algorithm exhibit additive time complexity in terms of angle and distance.

We use two metrics to measure the performance of the proposed ISF algorithm, which are achievable rate and normalized minimum mean square error (NMSE) criterion. The achievable rate refers to the information rate that the BS can receive by utilizing the estimated channel for beamforming, that is:

where $P_{s}$ is the power of source signal. If the Channel State Information (CSI) is perfect, the achievable rate is:

The NMSE is:

For a comparative analysis, the proposed codebook schemes are compared with the following schemes:

• •

  SWOMP: It is an angle domain on-grid algorithm [34]. It only searches for angles and not distances, making it suitable for far-field scenario rather than near-field.

• •

  SS-SIGW-OLS: It is an angle domain off-grid algorithm [35], which is only applicable to far-field search like the SWOMP algorithm. Due to its lack of grid quantization errors, its algorithm has higher precision.

• •

  P-SOWP: It is an on-grid algorithm in polar domain [32]. This algorithm divides the near-field space into different grids based on angle and distance, and then searches for which grid the UE is in. The angle division method is the same as the far-field, which is uniformly divided. The division method in terms of distance is non-uniform, with denser grids at closer distances.

• •

  P-SIGW: This is an off-grid algorithm in the polar domain [32], which is based on the P-SOWP algorithm and uses gradient descent to continue searching within the grid, ultimately determining the location of the UE.

• •

  MUSIC: This is a classic algorithm for far-field spatial spectrum estimation. Because in both JAC-ISF and JAC-GD algorithms, the estimation of $p_{2}$ is based on the MUSIC algorithm, we use the MUSIC algorithm as a comparison scheme to demonstrate to what extent the estimation of $p_{1}$ in the JAC scheme compensates for the error in estimating the near-field using the MUSIC algorithm.

Fig. 5 shows the comparison of achievable rates between proposed JAC-ISF, JAC-GD algorithms and MUSIC algorithm at different SNRs. All algorithms are performed with a snapshot points of 32. In this simulation experiment, the UE is located on the $z$-axis at a distance of 10 m to 50 m, which belonging to a deeper near-field range. We can see that when SNR=-10 dB, due to excessive noise, JAC-ISF cannot accurately estimate $p_{1}$, resulting in its performance being similar to the MUSIC algorithm. This indicates that the estimation of $p_{1}$ is close to complete failure at -10 dB. However, as the SNR increases, the JAC-ISF algorithm begins to significantly outperform the MUSIC algorithm. Especially when the SNR exceeds 5 dB, the performance of the JAC-ISF algorithm almost conforms to the bound curve. This experiment proves that, except for a few extreme scenarios, the JAC-ISF algorithm is effective in most cases. For JAC-GD, we can see that its performance is also better than the MUSIC algorithm at -10 dB, indicating that JAC-GD is still effective at low signal-to-noise ratios. And JAC-GD algorithm is closer to the solution under perfect CSI than JAC-ISF algorithm, which indicates the excellent performance of JAC-GD.

Fig. 6 shows the NMSE performance under different SNRs. The Fig. 6 (a) shows the curve for a snapshot points of 32. We can see that the proposed JAC-ISF and JAC-GD algorithms perform significantly better than other algorithms in the low SNR regime, but their performance limits are not as good as P-SIGW in the high SNR regime. This indicates that the JAC-ISF and JAC-GD algorithms have strong anti noise performance and are more stable in the presence of high noise levels. In the high SNR regime, the JAC-GD and JAC-ISF algorithms perform better than the SWOMP, SS-SIGW-OLS, and P-SOWP algorithms, but worse than the P-SIGW algorithm. This indicates that the upper performance limits of the JAC-ISF and JAC-GD algorithms are not as good as the P-SIGW algorithm, but in the SNR regime of normal communication scenarios, the JAC-ISF and JAC-GD algorithms perform better. Fig. 6 (b) shows the algorithm performance when the $T$ is 8. We found that compared to Fig. 6 (a), the P-SIGW algorithm requires higher SNRs to exceed the performance of JAC-ISF and JAC-GD. At this point, only when the SNR reaches 14 dB and 20 dB or above, can the performance of the p-algorithm surpass that of JAC-ISF and JAC-GD, respectively. In addition, we found that the performance curves of JAC-ISF and JAC-GD are not significantly different in Fig. 6 (a) and (b). This indicates that the performance of JAC-ISF and JAC-GD algorithms is less affected by the number of snapshots, and subsequent results will also demonstrate this.

Fig. 7 shows the NMSE performance vers distances. We can see that under the same snapshot points, the performance of the JAC-ISF algorithm is significantly better than other algorithms except the JAC-GD. We can find that when the communication distance is greater than 20 m, the JAC-ISF algorithm can save twice the number of snapshots compared to the P-SIGW algorithm. This indicates that the JAC-ISF algorithm is not only easy to implement, but also has low time complexity. For the JAC-GD algorithm, we can see that its performance at $T=8$ is even better than that of P-SIGW at $T=32$. This demonstrates the significant advantage of the JAC-GD algorithm in the low SNR regime.

Fig. 8 shows the performance comparison of various algorithms under different snapshot points, with the UE distance set to 10 m to 100 m. As illustrated in the Fig. 8, the performance of the JAC-ISF and JAC-GD algorithms remain basically unchanged as the number of snapshots increases. This is because in XL-MIMO, the number of spatial samples is relatively large, so even with just one snapshot, the spatial autocorrelation function can be accurately estimated, thereby accurately estimating the channel.

In the problem of location estimation, we use the Root Mean Squared Error (RMSE) criterion to measure algorithm performance, which can be written as:

where the ${\hat{\bm{p}}}$ is the estimated UE’s position, which can be obtained using $\hat{\theta}$ and $\hat{r}$.

Fig. 9-11 show the RMSE performance of various algorithms at different SNR, snapshot points, and distance. Due to the CRLB depends on $r$ in equation (40), we only present CRLB when comparing performance at different positions. The Fig. 9 shows the performance comparison at $T=8$. We can see that the JAC-GD algorithm performs well at low SNR regime. The JAC-ISF algorithm performs slightly better than P-SIGW in the low SNR range, but as the SNR increases, the trend of accuracy improvement in the JAC-ISF algorithm is not as fast as the other two algorithms. This shows that the JAC-ISF algorithm has performance advantages when resources are scarce, while the JAC-GD algorithm has performance advantages in most scenarios. The conclusion of Fig. 10 is similar to the above conclusion, that the JAC-ISF algorithm has performance advantages at less snapshot points, while the JAC-GD algorithm generally has performance advantages. In Fig. 11, we present the estimation results of $r$ and $\theta$ separately, and plot the CRLB as a benchmark. We can see that the JAC-GD algorithm is closest to the CRLB. This demonstrates that the JAC-GD algorithm not only has low time complexity, but also has significant performance advantages.