# Computationally Efficient Unitary ESPRIT Algorithm in Bistatic MIMO Radar

Authors: Baobao Liu; Tao Xue; Cong Xu; Yongjun Liu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

A low complexity unitary estimating signal parameter via rotational invariance techniques (ESPRIT) algorithm is presented for angle estimation in bistatic multiple-input-multiple-output (MIMO) radar. The devised algorithm only requires calculating two submatrices covariance matrix, which reduces the computation cost in comparison with subspace methods. Moreover, the signal subspace can be efficiently acquired by exploiting the NystrÖm method, which only needsOMNK2 flops. Thus, the presented algorithm has an essentially diminished computational effort, especially useful when K≪MN, while it can achieve efficient angle estimation accuracy as well as the existing algorithms. Several theoretical analysis and simulation results are provided to demonstrate the usefulness of the proposed scheme.


---

## Body

## 1. Introduction

Target estimation has been a significant problem in radar systems, which has been applied in widespread in sonar, guidance systems, speech processing, communication, medical signal processing, and other fields [1–3]. In recent years, considerable research interests have been drawn to MIMO radar [4–13], which exploits multiple antennas to emit diverse waveforms and utilizes multiple antennas to receive the echo signals [14]. This leads to its more underlying benefits over phased-array radar [15–17] (e.g., enhancing the spatial resolution, fading effect overcoming, and enhancing the parameter identifiability). MIMO radar can be regarded as an expansion of the phased-array radar, where the exploited waveforms are effectively independent [18]. Generally, MIMO radars can be divided into two types, the collocated MIMO radar and the statistical MIMO radar, based on the different array antenna configurations [19]. Furthermore, the collocated MIMO radars are categorised into two types, namely, the monostatic MIMO radar and the multistatic MIMO radar. Due to the fact that the emitting and receiving antennas are not in the identical location, the DOD and DOA estimation has become a considerable research matter [4, 18–21]. In our work, we mainly focus on the DOD and DOA estimation issue in the bistatic MIMO radar.According to the recent researches, several algorithms [4–10] have been proposed for estimation angle in the bistatic MIMO radar. In [4], the reduced-dimension multiple signal classification (MUSIC) algorithm that uses one-dimensional search is presented to angle estimation, which achieves high angle estimation accuracy in comparison with Capon algorithm [20]. In [5], the Capon algorithm is extended to DOD and DOA estimation, which has heavy computational complexity for requiring two-dimensional angle search. Moreover, the technique is subjected to some performance degradations for the proximate receiving steering vector. Besides, the estimation of angles needs peak searching with computational intensive. The root-MUSIC algorithm [6] without peak searching is presented by utilizing polynomial rooting technique to reduce the computational cost. In [7], the ESPRIT technique that uses the invariance technique of both the transmitting array and the receiving array is presented to estimate angle in the bistatic MIMO radar. However, the algorithm requires the pairing operation. In [8], to address the problem of automatic pairing, a combination ESPRIT-MUSIC algorithm is developed, which provides beneficial angle accuracy. In [9], a unitary ESRPIT technique that exploits the real-valued processing is devised for estimating angle in the bistatic MIMO radar, which has high estimation precision. In [10], the maximum likelihood algorithm is presented for direction finding estimation in MIMO radar. In [22], the novel joint angle estimation method is proposed by using tensor decomposition in the nested bistatic MIMO radar. Moreover, various methods are introduced for bistatic MIMO radar in [23–25]. However, the abovementioned algorithms have a large amount of computation since they require the calculation of sample covariance matrix (SCM) and its eigenvalue decomposition (EVD) to obtain the noise subspace or signal noise, especially for large MIMO radar array and a great deal of snapshots scenarios. In order to tackle this serious problem, a computationally efficient algorithm is devised for direction estimation in this work. Unlike the existing algorithms [4–10], the presented algorithm only requires to compute two submatrices of the SCM, which avoids calculating of SCM and its EVD by exploiting the NystrÖm technique. The proposed method can be also applied in the nonuniform linear array, L-shape array, and uniform circular array for angle estimation. The NystrÖm method has been extensively applied in speed up methods [26, 27] and is first utilized by Williams and Seeger [27] for sparsifying kernel matrices. By exploiting the NystrÖm method [28, 29], we extend the previous work [30] and develop a low complexity unitary ESPRIT algorithm which not only has high angle estimation precision but also obtains light computational cost, especially in large MIMO radar array scenario. In this paper, we derive a new powerful unitary ESPRIT approach, which exhibits many benefits as follows: (a) it has much lower computational cost than that of the ESRPIT and unitary ESPRIT methods; (b) it enjoys higher angle estimation precision than the ESPRIT algorithm; (c) it is suitable for direction finding estimation of large MIMO radar array. The benefits of the presented algorithm are shown by some simulation experiments.


## 2. Data Model

In this paper, we think about a bistatic MIMO radar system (Figure1) constituted of M-transmitting antenna array and N-receiving antenna array, both of which are half-wavelength spaced uniform linear arrays [7–9]. Assume that there exist P noncoherent targets located in the same range bin. The DOD and DOA of the pth target relative to the transmitting array normal and the receiving array normal are denoted by θp and ϕpp=1,2,…,P, respectively. Thus, the signal model can be given as [7, 8](1)yt=Ast+nt,where A=a1,a2,…,aP denotes an MN×P matrix consisting of the P steering vectors and ap=arϕp⊗atθp illustrates the Kronecker product of the receiving array steering vector and the transmitting array steering vector for the pth source. arϕp and atθp are respectively rewritten as(2)arϕp=1,expjπvp,…,expjπN−1vpT,atθp=1,expjπup,…,expjπM−1upT,and up=sinθp,vp=sinϕp, where ϕp and θp represent the DOA and DOD, respectively. st=s1t,s2t,…,sPtT is a column vector, in which spt=αpej2πfdpt denotes the envelope of the reflected signal with αp being the amplitude containing the reflection coefficients and path losses and so on [7–9]. nt denotes an MN×1 complex Gaussian white noise vector with zero mean and covariance matrix σ2IMN.Figure 1
Radar configuration.


## 3. NystrÖm Method-Based Unitary ESPRIT for Angle Estimation

### 3.1. Real-Valued Processing

In order to reduce computational complexity, we have to transform the complex data to real data by matrix method since the array, the received data, is complex data. LetY be represented as the data matrix consisting of L snapshots ytl, 1≤l≤L. The augmented data matrix is defined as Z=YΠMNY∗ΠL, where ΠMN represents the exchange matrix including J ones on its antidiagonal and zeros elsewhere. Then, the real-valued matrix is expressed as [9, 11](3)Γ=QMNHZQ2L,where QJ signifies sparse unitary matrix, expressed as(4)Q2J=12IJjIJΠJ−jΠJ,Q2J+1=12IJ0jIJ0T20TΠJ0−jΠJ.


### 3.2. Signal Subspace Estimation

To use the NystrÖm technique [27, 28] for estimating angle, we disintegrate the matrix Γ as follows [30]:(5)Γ=Γ1Γ2,where Γ1∈ℝK×L and Γ2∈ℝMN−K×L are the real-valued submatrices received by the first K antenna and the rest of the MN−K antennas, respectively. We define(6)R11=EΓ1Γ1H,R21=EΓ2Γ1H.Moreover, we must ensure thatR11 denotes full rank matrix where K satisfies K|P≤K≤minMN,L, K=1,2,…,MN. It is noted that K has not been required to ascend substantially with MN. For instance, when MN grows from 10 to 30, a relatively little K, such as K=12, is sufficient to insure estimating precision, which also reduces the computational complexity.Suppose that the EVD ofR11 is U11Λ11U11H, where U11∈ℂK×K denotes the eigenvector matrix and Λ11 represents the diagonal matrix. Defining U21≜R21U11Λ11−1, we can constitute a new matrix as follows [30]:(7)U≜U11U21.Then, according to the results from the remark, we can obtain the signal subspace without the computation of SCM and its EVD.Remark 1 (see [30]).
Suppose that the EVD ofGHG is UGΛGUGH and G=UΛ111/2, where ΛG=diagλG1,…,λGK denotes the eigenvalue matrix with λG1≥⋯≥λGK and UG=uG1,…,uGK represents the corresponding eigenvector matrix with uGii=1,…,K being the ith eigenvector. Then, the signal subspace is constructed by the first P column vectors of Π as follows:(8)spanEs=spanA,where Es≜Π:,1:PandΠ=GUG.


### 3.3. Angle Estimation

Then, according to the unitary ESPRIT algorithm [9, 11], the real-valued invariance relation is described as follows:(9)F2θdp=tanπup2F1θdp,where F1θ=ReQM−1NHdiagNJ2θQMN and F2θ=ImQM−1NHdiagNJ2θQMN denote real-valued matrix, respectively, and J2θ is defined in [9, 11]. dp=QMNHap denotes a steering vector that is real-valued. Thus, F2θEs=F1θEsΨθ represents the real-valued invariance equation for the transmitter array where Ψθ=T−1ΦθT and Φθ=diagtanπu1/2,tanπu1/2,…,tanπup/2 signifies a real-valued diagonal matrix whose diagonal elements include information of estimating DOD [9, 11]. In the receiving array, similarly, the real-valued invariance equation is constructed by(10)F2ϕEs=F1ϕEsΨϕ,where F1ϕ=ReQM−1NHJ2ϕQMN and F2ϕ=ImQM−1NHJ2ϕQMN, J1ϕ=IMN−1×MN−10MN−1×M and J2ϕ=0MN−1×MIMN−1×MN−1, Ψϕ=T−1ΦϕT, Φϕ=diagtanπv1/2,tanπv2/2,…,tanπvp/2, and T stands for a nonsingular matrix. Φθ represents a real-valued diagonal matrix whose diagonal elements include information of estimating DOA. Then, Ψθ+jΨφ is described as [9, 11](11)Ψθ+jΨφ=T−1Ψθ+jΨT.Then, the DODs and DOAs can be estimated by(12)θ^p=arcsin2arctanΦθppπ,p=1,…,P,ϕ^p=arcsin2arctanΦϕppπ,p=1,…,P.


## 3.1. Real-Valued Processing

In order to reduce computational complexity, we have to transform the complex data to real data by matrix method since the array, the received data, is complex data. LetY be represented as the data matrix consisting of L snapshots ytl, 1≤l≤L. The augmented data matrix is defined as Z=YΠMNY∗ΠL, where ΠMN represents the exchange matrix including J ones on its antidiagonal and zeros elsewhere. Then, the real-valued matrix is expressed as [9, 11](3)Γ=QMNHZQ2L,where QJ signifies sparse unitary matrix, expressed as(4)Q2J=12IJjIJΠJ−jΠJ,Q2J+1=12IJ0jIJ0T20TΠJ0−jΠJ.


## 3.2. Signal Subspace Estimation

To use the NystrÖm technique [27, 28] for estimating angle, we disintegrate the matrix Γ as follows [30]:(5)Γ=Γ1Γ2,where Γ1∈ℝK×L and Γ2∈ℝMN−K×L are the real-valued submatrices received by the first K antenna and the rest of the MN−K antennas, respectively. We define(6)R11=EΓ1Γ1H,R21=EΓ2Γ1H.Moreover, we must ensure thatR11 denotes full rank matrix where K satisfies K|P≤K≤minMN,L, K=1,2,…,MN. It is noted that K has not been required to ascend substantially with MN. For instance, when MN grows from 10 to 30, a relatively little K, such as K=12, is sufficient to insure estimating precision, which also reduces the computational complexity.Suppose that the EVD ofR11 is U11Λ11U11H, where U11∈ℂK×K denotes the eigenvector matrix and Λ11 represents the diagonal matrix. Defining U21≜R21U11Λ11−1, we can constitute a new matrix as follows [30]:(7)U≜U11U21.Then, according to the results from the remark, we can obtain the signal subspace without the computation of SCM and its EVD.Remark 1 (see [30]).
Suppose that the EVD ofGHG is UGΛGUGH and G=UΛ111/2, where ΛG=diagλG1,…,λGK denotes the eigenvalue matrix with λG1≥⋯≥λGK and UG=uG1,…,uGK represents the corresponding eigenvector matrix with uGii=1,…,K being the ith eigenvector. Then, the signal subspace is constructed by the first P column vectors of Π as follows:(8)spanEs=spanA,where Es≜Π:,1:PandΠ=GUG.


## 3.3. Angle Estimation

Then, according to the unitary ESPRIT algorithm [9, 11], the real-valued invariance relation is described as follows:(9)F2θdp=tanπup2F1θdp,where F1θ=ReQM−1NHdiagNJ2θQMN and F2θ=ImQM−1NHdiagNJ2θQMN denote real-valued matrix, respectively, and J2θ is defined in [9, 11]. dp=QMNHap denotes a steering vector that is real-valued. Thus, F2θEs=F1θEsΨθ represents the real-valued invariance equation for the transmitter array where Ψθ=T−1ΦθT and Φθ=diagtanπu1/2,tanπu1/2,…,tanπup/2 signifies a real-valued diagonal matrix whose diagonal elements include information of estimating DOD [9, 11]. In the receiving array, similarly, the real-valued invariance equation is constructed by(10)F2ϕEs=F1ϕEsΨϕ,where F1ϕ=ReQM−1NHJ2ϕQMN and F2ϕ=ImQM−1NHJ2ϕQMN, J1ϕ=IMN−1×MN−10MN−1×M and J2ϕ=0MN−1×MIMN−1×MN−1, Ψϕ=T−1ΦϕT, Φϕ=diagtanπv1/2,tanπv2/2,…,tanπvp/2, and T stands for a nonsingular matrix. Φθ represents a real-valued diagonal matrix whose diagonal elements include information of estimating DOA. Then, Ψθ+jΨφ is described as [9, 11](11)Ψθ+jΨφ=T−1Ψθ+jΨT.Then, the DODs and DOAs can be estimated by(12)θ^p=arcsin2arctanΦθppπ,p=1,…,P,ϕ^p=arcsin2arctanΦϕppπ,p=1,…,P.


## 4. Computational Complexity and Cramér-Rao Bound (CRB)

The presented technique does not need utilizing the whole SCM. Instead, it requires calculatingR11 and R21 which need OLK2 and OMNLK−LK2 flops, respectively. Meanwhile, the signal subspace is constructed by exploiting the NystrÖm approach, where the computational complexity is OMNK2. Thus, the presented method requires OMNLK+MNK2. However, the classical unitary ESPRIT and ESPRIT algorithms need OM2N2L+M3N3/4 and OM2N2L+M3N3 flops, respectively, which are much higher than OMNLK+MNK2 flops on condition that K≪minMN,L. Furthermore, referring to [11], we use CRB in simulation as follows:(13)CRB=σ22LReDHΠA⊥⊙P^wT−1,where(14)D=∂a1∂θ1,∂a2∂θ2,…,∂ak∂θk,∂a1∂ϕ1,∂a2∂ϕ2,…,∂ak∂ϕk,ΠA⊥=IMN−AAHA−1AH,P^w=P^sP^sP^sP^s,P^s=1L∑t=1LstsHt.


## 5. Simulation Results

In this installment, a vast number of computer simulations are demonstrated to prove the effectiveness of the proposed technique. We compare performance of the estimating angle of the presented method with the ESPRIT algorithms [7] and unitary ESPRIT [9] and present their computational complexity analysis. In the following simulation experiments, 200 Monte-Carlo iterations are adopted for the bistatic MIMO radar in the experiments. We suppose that there exist three noncoherent targets and their location is at angles θ1,ϕ1=10°,20°, θ2,ϕ2=−8°,30°, and θ3,ϕ3=0°,45°, respectively. The root mean squared error (RMSE) of over angle [9] is exploited in the simulation experiments.Figures2 and 3 describe the angle estimation paired results of the presented scheme with SNR = 10 dB and SNR = 10 dB, respectively. It can be shown that the transmit angles (DODs) and receive angles (DOAs) can be clearly seen. Figure 3 also implies that the presented scheme can efficiently estimate angle of the targets in low SNR scenario.Figure 2
Paired results with SNR = 10 dB,M=8, N=6, and L=200.Figure 3
Paired results with SNR = 5 dB,M=8, N=6, and L=200.Figures4 and 5 demonstrate performance comparison of the estimating angle with M=8, N=6 and M=6, N=6, respectively. We compare the presented technique with the ESPRIT and the unitary ESPRIT methods. Figures 4 and 5 demonstrate that the proposed algorithm has much better estimation precision than the ESPRIT method and enjoys high estimation precision that is almost the same as the unitary ESPRIT scheme at high SNR range. However, the presented algorithm is somewhat inferior to the unitary ESPRIT scheme at the low SNR scenario.Figure 4
RMSE withM=8, N=6, and L=50.Figure 5
RMSE withM=6, N=6, and L=50.Figures6–9 show performance comparison of estimation of the presented technique with L=50 and L=100 for different M/N, respectively. From Figures 6–9, we can find that the angle estimation precision of the presented scheme is significantly enhanced with the number of transmitting array elements/receiving array elements increasing. Multiple receiving/transmitting array elements enhance estimation precision owing to diversity gain.Figure 6
RMSE withL=50 and different M.Figure 7
RMSE withL=100 and different M.Figure 8
RMSE withL=50 and different N.Figure 9
RMSE withL=100 and different N.Figures10 and 11 illustrate estimation precision comparison of the presented technique with M=6 and N=6 for different values of L, respectively. As shown in Figures 10 and 11, the estimation precision of the presented technique is boosted with L increasing. Meanwhile, Figure 10 also indicates that the presented method has beneficial estimation precision at small number of snapshots scenario.Figure 10
RMSE withM=6, N=6, and different L.Figure 11
RMSE withM=6, N=6, and different L.Figures12–14 illustrate the complexity comparison with K=5,10,15, where we can find the proposed algorithm has much less computational cost in comparison with the ESPRIT and the unitary ESPRIT schemes, particularly when M=N becomes larger.Figure 12
Complexity comparison withL=200.Figure 13
Complexity comparison withL=400.Figure 14
Complexity comparison againstL with M=N=10.Figure15 and Table 1 describe the runtime of the three ESPRIT schemes. They depict the average CPU time required to calculate each ESPRIT approach on the personal computer with Intel(R) core(TM) 2 Duo CPU T3700 processor. We can clearly observe that the presented approach is much more computationally effective than the existing schemes, especially when M=N becomes bigger.Figure 15
Runtime comparison versusM=N with L=100 and K=12.Table 1
Computations time comparison (P=3, L=100, K=12, and SNR = 10 dB).
Transmit and receive elementsUnitary ESPRIT average runtime (s)ESPRIT average runtime (s)Proposed method average runtime (s)M=N=100.010230.010810.00089M=N=150.043290.055030.00132M=N=200.182800.274400.00234M=N=250.598900.948000.00397M=N=301.602002.906000.00654


## 6. Conclusion

In this paper, we have developed a low complexity unitary ESPRIT method for estimating angle in the bistatic MIMO radar. Compared with the existing unitary ESPRIT and ESPRIT algorithms which requireOM2N2L+M3N3/4 and OM2N2L+M3N3 flops, respectively, our approach only needs O2MNLK+MNK2 flops, thereby being much more computationally effective, especially for the case of a large MIMO radar array. Moreover, extensive simulation results demonstrate that the estimation precision of the presented scheme is much higher by comparison with the ESPRIT method and very similar to the unitary ESPRIT algorithm. In the future research, the presented technique can be extended to a different application such as estimating angle in the monostatic MIMO radar.



---

*Source: 5584688-2021-06-17.xml*