# Two-Dimensional Direction-of-Arrivals Estimation Based on One-Dimensional Search Using Rank Deficiency Principle

Authors: Feng-Gang Yan; Zhi-Kun Chen; Ming-Jian Sun; Yi Shen; Ming Jin
Journal: International Journal of Antennas and Propagation
 (2015)

---

## Abstract

A novel efficient method for two-dimensional (2D) direction-of-arrivals (DOAs) estimation is proposed to reduce the computational complexity of conventional 2D multiple signal classification (2D-MUSIC) algorithm with uniform rectangular arrays (URAs). By introducing two electrical DOAs, the formula of 2D-MUSIC is transformed into a new one-dimensional (1D) quadratic optimal problem. This 1D quadratic optimal problem is further proved equivalent to finding the conditions of noise subspace rank deficiency (NSRD), which can be solved by an efficient 1D spectral search, leading to a novel NSRD-MUSIC estimator accordingly. Unlike 2D-MUSIC with exhaustive 2D search, the proposed technique requires only an efficient 1D one. Compared with the estimation of signal parameter via rotation invariance techniques (ESPRIT), NSRD-MUSIC has a significantly improved accuracy. Moreover, the new algorithm requires no pair matching. Numerical simulations are conducted to verify the efficiency of the new estimator.


---

## Body

## 1. Introduction

Estimation of direction-of-arrival (DOA) of multiple narrow-band signals using sensor arrays is of great interest in many fields such as radar, sonar, and wireless communications [1, 2]. Over several decades, this topic has been extensively addressed and numerical algorithms have been developed. Among those approaches, the multiple signal classification (MUSIC) [3] algorithm firstly exploits the orthogonality between the signal and the noise subspaces to achieve a so-called superresolution DOA estimate. Because those two subspaces are perfectly orthogonal to each other when the signal-to-noise ratio (SNR) is sufficiently high, the MUSIC algorithm can resolve two sources as closely spaced as possible in theory. Another outstanding advantage of the MUSIC algorithm over the other superresolution methods is that the former can be used with arbitrary array geometries [4]. However, the computational complexity of MUSIC is prohibitively expensive for real-time applications, owing to an involved matrix decomposition step for the signal or/and the noise subspace estimation and a tremendous spectral search step for final DOA estimates [5].In practical applications, it is two-dimensional (2D) DOAs (2D DOAs) (i.e., elevation and azimuth angles) that people are usually most concerned about. Estimators such as MUSIC and estimation of signal parameter via rotation invariance technique (ESPRIT) [6] have been studied in one-dimensional (1D) situations and further extended to 2D scenarios [7]. Due to the increase in the dimensionality of the 2D DOA estimation problem, the complexity of DOA estimation process is severely affected by the array geometry [8], and further the pair matching (i.e., association or alignment) of the estimated elevation and azimuth angles is usually required [9]. Since, for arbitrary array configurations, the elevation and azimuth angles are extremely coupled with each other in the array response manifold, the heavy 2D spectral search cannot be avoided. To reduce the complexity, researchers are obliged to focus on reducing the computational burden of the 2D DOA estimation problem with various specified array structures.Planar sensor arrays composed of two or more uniform linear arrays (ULAs) with simple geometry configurations have received considerable attention. Exploiting specified geometries such as L-shaped [10, 11], Y-shaped [12], and Z-shaped arrays [13], 2D DOAs of multiple incident signals can be estimated with reduced computational burden by applying most 1D subspace-based estimation methods including MUSIC and ESPRIT. Special array configurations allow utilizing the shift invariance and the partition of array response vector of two overlapping subarrays of each ULA such that the signal or/and noise subspaces can be estimated without eigenvalue decomposition (EVD) or singular valued decomposition (SVD). Nevertheless, spectral search is still required for those methods, and, as a matter of fact, the complexity of spectral search is substantially heavier than that of subspace decomposition, especially for 2D DOAs estimates [14]. Moreover, because the total arrays are usually divided into several subarrays in those methods, the array aperture is in fact reduced and DOA estimation accuracy may be sacrificed [15].Uniform rectangular array (URA) is another frequently discussed array structure. A geometric formulation of the ESPRIT algorithm exploiting subarrays of URA is presented to reparameterize the weighted subspace fitting (WSF) algorithm in [16], leading naturally to an extension to the 2D DOA estimation problem. With high dimensional signal processing, the 2D subspace-based algorithms in [17] can provide precise estimates at the expense of high computational complexity exponentially increasing with the size of the rectangular arrays. To reduce the computational load, a tree structure algorithm by first performing 1D spatial smoothing and then 1D MUSIC several times successively is proposed in [18] to estimate the azimuth and elevation angles independently. Despite the computational efficiency, almost all of the aforementioned techniques realize 2D DOA estimates at the cost of a reduction in array aperture.Recently, an outstanding reduced-dimensional MUSIC (RD-MUSIC) algorithm is proposed to avoid the high computational cost within 2D-MUSIC for direction of departure (DOD) and DOA estimation in multiinput multioutput (MIMO) radar [19]. Using DOA information embedded in the velocity sensors, RD-MUSIC starts 1D MUSIC searches for the DOD and DOA in succession without parameter pairing nor 2D search. In fact, the formula of RD-MUSIC is somewhat similar to that of 2D DOA estimates except that the noise projection matrix in the former is of reduced order and is invertible while that of the latter is not. Following this idea, we present in this paper a new efficient technique for 2D DOAs estimation with URAs. With two introduced electrical angles, we show that the formula of 2D-MUSIC can be transformed into a new 1D quadratic optimal problem. Further analysis demonstrates that this 1D quadratic optimal problem is equivalent to finding the conditions of noise subspace rank deficiency (NSRD), which can be solved by an efficient 1D spectral search. Consequently, a novel NSRD-MUSIC estimator at hand is derived. Unlike 2D-MUSIC with exhaustive 2D search, the proposed technique requires only an efficient 1D one. Compared with ESPRIT, NSRD-MUSIC has a significantly improved Root Mean Square Error (RMSE) performance.The outline of this paper is as follows. The narrow-band signal model and the conventional 2D-MUSIC algorithm are introduced in Section2. Two transformed electrical angles reformulating the 2D-MUSIC algorithm into a new 1D optimum problem is then considered, and the proposed method is addressed in detail in Section 3. The complexity of our method is analyzed in Section 4 and simulation results are conducted and discussed to validate the effectiveness of new method in Section 5.


## 2. Signal Model and Standard 2D-MUSIC

Assume that there areK narrow-band signals with unknown 2D DOAs θ,ϕ≜θ1,ϕ1,θ2,ϕ2,…,θK,ϕK simultaneously incident on URA of M=MxMy sensors, where Mx and My are the numbers of elements in x-direction and y-direction, respectively. The corresponding element spacing symbols are dx and dy, as depicted in Figure 1. The azimuth angle θ is defined as the one between the wave direction and the z-axis while the elevation angle ϕ is defined as the one between the x-axis and the projection of wave direction onto the x-y plane. Note that θ∈[0,π/2] and ϕ∈[0,2π]. It is assumed that there are N snapshots available; M×1 array output vector at snapshot t is given by(1)xt=Ast+nt,t=1,…,N,where(2)A=aθ1,ϕ1,aθ2,ϕ2,…,aθK,ϕKis the M×K matrix of the signal direction vectors and(3)aθ,ϕ=1ej2π/κcdxsin⁡θcos⁡ϕ+dysin⁡θsin⁡ϕ⋮ej2π/κcMx-1dxsin⁡θcos⁡ϕ+My-1dysin⁡θsin⁡ϕis the M×1 steering vector. In addition, j≜-1 and st is the K×1 vector of source waveforms; nt is the M×1 vector of white sensor noise; κc is the center wavelength; ·T is the matrix transpose.Figure 1
Array geometry of the URA.The estimate of theM×M array output covariance matrix (AOCM)(4)R=ExtxHt=ARsAH+σn2IMis given by(5)R^=1N∑t=1NxtxHt,where Rs=E(stsHt) is K×K signal covariance matrix; I is M×M identity matrix; σn2 is the noise variance; E(·) is the mathematical expectation; and (·)H is the matrix Hermitian transpose.


### 2.1. Subspace Decomposition and 2D-MUSIC Algorithm

The EVDs of the theoretical AOCM (4) and the practical estimated AOCM (5) can be defined in a standard way:(6)R=VsΠsVsH+VnΠnVnH,R^=V^sΠ^sV^sH+V^nΠ^nV^nH,where(7)Vs=v1,…,vK,Vn=vK+1,…,vM,Πs=diagπ1,…,πK,Πn=diagπK+1,…,πM,V^s=v^1,…,v^K,V^n=v^K+1,…,v^M,Π^s=diagπ^1,…,π^K,Π^n=diagπ^K+1,…,π^Mwith the subscripts s and n standing for the signal and noise subspace, respectively.Based on the orthogonality betweenspanVs and spanVn, conventional 2D-MUSIC algorithm [3] suggests searching the following function:(8)P2D-MUSICθ,ϕ=1aHθ,ϕV^nV^nHaθ,ϕover the total 2D angular field-of-view 0,π/2×0,2π with a fine grid. K peaks of P2D-MUSICθ indicate source DOAs. One of the advantages of the 2D-MUSIC algorithm over other subspace-based methods is its nondependence on array configurations [4]. However, the complexity of this spectral search step is typically substantially high since, for each point, the product aHθ,ϕV^nV^nHaθ,ϕ has to be computed.


## 2.1. Subspace Decomposition and 2D-MUSIC Algorithm

The EVDs of the theoretical AOCM (4) and the practical estimated AOCM (5) can be defined in a standard way:(6)R=VsΠsVsH+VnΠnVnH,R^=V^sΠ^sV^sH+V^nΠ^nV^nH,where(7)Vs=v1,…,vK,Vn=vK+1,…,vM,Πs=diagπ1,…,πK,Πn=diagπK+1,…,πM,V^s=v^1,…,v^K,V^n=v^K+1,…,v^M,Π^s=diagπ^1,…,π^K,Π^n=diagπ^K+1,…,π^Mwith the subscripts s and n standing for the signal and noise subspace, respectively.Based on the orthogonality betweenspanVs and spanVn, conventional 2D-MUSIC algorithm [3] suggests searching the following function:(8)P2D-MUSICθ,ϕ=1aHθ,ϕV^nV^nHaθ,ϕover the total 2D angular field-of-view 0,π/2×0,2π with a fine grid. K peaks of P2D-MUSICθ indicate source DOAs. One of the advantages of the 2D-MUSIC algorithm over other subspace-based methods is its nondependence on array configurations [4]. However, the complexity of this spectral search step is typically substantially high since, for each point, the product aHθ,ϕV^nV^nHaθ,ϕ has to be computed.


## 3. The Proposed Algorithm

The 2D steering vector given in (3) represents the nominal array response. Following the notation in [20], a(θk,ϕk),k=1,…,K can be rewritten as(9)aθk,ϕk=axψx⊗ayψy,k=1,…,K,where ⊗ denotes the Kronecker product and the elements of vectors axψx and ayψy are given by(10)axψxmx=ej2π/κcψxmx-1,mx=1,…,Mx,ayψxmy=ej2π/κcψymy-1,my=1,…,My,where ·m denote the mth element of the embraced vector. Electrical angles ψx and ψy are related to the physical azimuth and elevation angles by(11)ψx=dxsin⁡θcos⁡ϕ,ψy=dysin⁡θsin⁡ϕ and the corresponding inverse relations for obtaining azimuth and elevation angles are(12)ϕ=tan-1⁡dydxψyψx,θ=sin-1⁡ψx2dx2+ψy2dy2.Let us define(13)Pψx,ψy≜axψx⊗ayψyHVnVnHaxψx⊗ayψy.Then the spectral search involved in the 2D-MUSIC algorithm is equivalent to the following optimization problem:(14)minψx,ψyP^ψx,ψys.t.ψx,ψy∈-dx,dx×-dy,dy.Observing that ax(ψx)⊗ay(ψy)=ay(ψy)⊗IMxax(ψx), (13) can be rewritten as(15)Pψx,ψy=axHψxayψy⊗IMxHVnVnHayψy⊗IMxaxψx≜axHψxQψyaxψx, where(16)Qψy≜ayψy⊗IMxHVnVnHayψy⊗IMx.Therefore, the optimization problem in (14) can be reconstructed as follows:(17)minψx,ψyaxHψxQ^ψyaxψxs.t.ψx,ψy∈-dx,dx×-dy,dy.To solve the above quadratic optimization, it is suggested in [19] to use the following constraint:(18)e1Haxψx=1,e1≜1,0,…,0︸Mx-1zeros to eliminate the trivial solution ax(ψx)=0, leading to a so-called RD-MUSIC estimator with the following search function:(19)PRD-MUSICψy=Q^ψy-11,1, where ·(1,1) is the (1,1)th element of the embraced matrix. The electrical angle ψyk,k=1,…,K can be estimated by an efficient one-dimensional spectral search over -dy,dy for K largest peaks of PRD-MUSICψy. However, the constraint e1Hax(ψx)=1 in fact only warrants that the first element of ax(ψx) equals one. We now propose a new NSRD-MUSIC method which has a similar computational complexity as compared to the RD-MUSIC algorithm.Becauseax(ψx)≠0, it is clear that(20)axHψxQψyaxψx=0 holds if and only if Mx×Mx matrix Qψy is of rank deficiency; that is,(21)axHψxQψyaxψx=0⟺rankQψy<Mx.Noting that [21](22)rankayψy⊗IMx=rankayψy·rankIMx=Mx,rankVnVnH=rankVn=M-K, for M-K≥Mx or equivalently for(23)K≤M-Mx,Qψy is a rank-deficient matrix if and only if ψy is the electrical angle of source DOAs. Therefore, we have(24)rankQψy<Mx⟺ψyk=dysin⁡θksin⁡ϕk,k=1,…,K.Based on the above analysis, K electrical angle that related the source DOAs, that is, ψyk,k=1,…,K, can be estimated by searching(25)PNSRD-MUSICψy=1EigminQ^ψyor equivalently by searching(26)PNSRD-MUSICψy=1DetQ^ψyover -dy,dy for K largest peaks of PNSRD-MUSICψy. Here, Eigmin[·] and Det[·] stand for the minimum eigenvalue and the determinant of the embraced matrix, respectively. K angles relating to K largest peaks of PNSRD-MUSICψy should be the electrical angles ψyk,k=1,…,K.Withψyk,k=1,…,K, we can compute K steering vectors corresponding to ψxk,k=1,…,K as follows [19]:(27)axψxk=Qψyk-1e1e1HQψyk-1e1,k=1,…,K.Combing (10) and (27) leads to(28)gk≜-∠axψxk=012⋮Mx-12πκcψxkk=1,…,K,where ∠· stands for phase angles for each element of the embrace vector. We now exploit the least squares (LS) principle to estimate ψ^xk,k=1,…,K. Define(29)P≜1011121⋮1Mx-1,ξk≜02πκcψxk.Then we have(30)Pξk=gk,k=1,…,K. The LS solution for estimating ξ^k with g^k is given by (31)ξ^k=PTP-1PTg^k,k=1,…,K.Using (29) and (31), ψxk,k=1,…,K is estimated by(32)ψ^xk=κc2πξ^k2,k=1,…,K.Now, we have estimatedK electrical angles ψyk,k=1,…,K and ψxk,k=1,…,K. Since, for each ψyk,k∈[1,K], we can compute a corresponding ψxk,k∈[1,K] by using (27)–(32), no further pair matching is required for the proposed algorithm. Hence, we can directly insert (ψ^xk,ψ^yk),k=1,…,K, into (12) to finally obtain the estimates of the azimuth and elevation angles (θ^k,ϕ^k),k=1,…,K.


## 4. Complexity Analysis and Summary

Comparison of primary complexity among three algorithms including 2D-MUSIC [3], RD-MUSIC [19], and the proposed NSRD-MUSIC is shown in Table 1, where Jθ, Jϕ, and Jψy stand for the search numbers along the directions of θ, ϕ, and ψy, respectively. The common term OM2K gives the complexity of EVD on R [21]. Because 2D-MUSIC involves a 2D spectral search step, it has to compute Jθ·Jϕ spectral points. Since RD-MUSIC and the proposed method involve a 1D search step, the two techniques only need to compute Jψy spectral points. Generally, we have Jθ≈Jϕ≈Jψy≫M>K. Therefore, NRSD-MUSIC has a much lower complexity than 2D-MUSIC.Table 1
Complexity in terms of real-valued operations.
Algorithms
Primary computations
2D-MUSIC
O
M
2
K
+
O
J
θ
⋅
J
ϕ
(
M
+
1
)
(
M
-
K
)
RD-MUSIC [19]
O
M
2
K
+
O
J
ψ
y
M
x
2
K
NSRD-MUSIC
O
M
2
K
+
O
J
ψ
y
M
x
2
KDetailed steps for implementing the proposed NSRD-MUSIC algorithm are summarized in Algorithm1.Algorithm 1:The proposed NSRD-MUSIC algorithm.
Require: {x^t}t=1N: N snapshots of received datum.
(1) Initiation:R^=0,k=1/N.
(2)for  i=1; i≤N; i++  do
(3)R^=R^+kx(i)xH(i);
(4)end for
(5) ComputeR^=V^sΠ^sV^sH+V^nΠ^nV^nH.
(6)foreach ψy∈-dy,dy  do
(7)Compute Qψy=ay(ψy)⊗IMxHVnVnHay(ψy)⊗IMx;
(8)Calculate PNSRD-MUSICψy by (25) or by (26);
(9)end for
(10) Find{ψyk}k=1K relating to the K largest peaks of PNSRD-MUSICψy;
(11) Insert{ψyk}k=1K into (27), (28) and compute {ψxk}k=1K by (32);
(12) Insert{(ψ^xk,ψ^yk)}k=1K into (12) to obtain {(θ^k,ϕ^k)}k=1K.
(13)return  {(θ^k,ϕ^k)}k=1K: estimated azimuth and elevation angles.


## 5. Simulation Results

Simulations with 500 independent Monte Carlo methods have been conducted on UCR composed ofMx×My=3×3=9 sensors with half wavelength apart along both x- and y-axis to assess the performance of the proposed estimator. It is assumed that there are K=3 sources at (θ1=10∘, ϕ1=20∘), (θ2=30∘, ϕ2=35∘), and (θ3=40∘, ϕ3=150∘) that are implying on the array from far-field. The RMSEs for the estimates of source incident angles θ and ϕ are defined as (33)RMSEθ≜1500∑i=1500θ^i-θ2,(34)RMSEϕ≜1500∑i=1500ϕ^i-ϕ2,respectively, where θ and ϕ are the true 2D DOAs while ϕ^i and θ^i represent the estimated values of the elevation and azimuth angles of the ith trial.Figures2 and 3 plot the spectrums of three functions including 2D-MUSIC, RD-MUSIC [19], and the proposed estimator. It is seen from the figures that the proposed method estimates ψy correctly, which generates corresponding peaks at ψy1=sin⁡(θ1)cos⁡(ϕ1)=sin⁡10∘cos⁡(20∘)≈0.16, ψy2=sin⁡θ2cos⁡(ϕ2)=sin⁡30∘cos⁡(35∘)≈0.41, and ψy3=sin⁡θ3cos⁡(ϕ3)=sin⁡40∘cos⁡(150∘)≈-0.56 as expected. This indicates that ψy can be estimated by the proposed method with 1D spectral search efficiently. Therefore, the proposed method has a much lower computational complexity as compared to 2D-MUSIC.Figure 2
Spectrum of 2D-MUSIC.Figure 3
Spectrums of RD-MUSIC and the proposed.Figures4 and 5 compare the estimation RMSEs of θ by four algorithms including 2D-MUSIC, 2D-ESPRIT, RD-MUSIC, and the proposed method. In Figure 4, the results are plotted against the SNR, where the number of snapshots is set as N=200. In Figure 5, the results are given as functions of the number of snapshots, where SNR = 10 dB. Note that all the estimation accuracies in both Figures 4 and 5 are respected to the source at (θ2=30∘, ϕ2=35∘). It can be concluded form Figure 4 that the proposed method provides a significantly improved accuracy performance as compared to 2D-ESPRIT over the total range of SNR = −9 dB to SNR = 15 dB. This is because the array aperture is in fact reduced in 2D-ESPRIT while that is not in the proposed method. It can be also concluded form Figure 4 that our method has a very close accuracy to RD-MUSIC and 2D-MUSIC, especially for SNR>3dB. On the other hand, we can see clearly from Figure 4 that the proposed estimator provides an asymptotically similar accuracy performance to RD-MUSIC and 2D-MUSIC, which is much better than 2D-ESPRIT.Figure 4
RMSE ofθ against the SNR.Figure 5
RMSE ofθ against the number of snapshots.To further compare the performance of the new method with performances of 2D-MUSIC, 2D-ESPRIT, and RD-MUSIC, Figures6 and 7 give the estimation RMSEs of ϕ by different algorithms. The results in Figure 4 are plotted against the SNR while those in Figure 5 are plotted as functions of the number of snapshots. In Figure 4, the number of snapshots is set as N=200 and in Figure 5 it is fixed as SNR = 10 dB. Similarly, all the results in Figures 6 and 7 are respected to the source at (θ2=30∘, ϕ2=35∘). It can be concluded again form Figures 6 and 7 that our method significantly outperforms 2D-ESPRIT, which provides an asymptotically similar accuracy performance to 2D-MUSIC and RD-MUSIC.Figure 6
RMSE ofϕ against the SNR.Figure 7
RMSE ofϕ against the number of snapshots.Finally, we evaluate the performance of the proposed method against the correlation between the incident signals. We consider the case of three signalss1(t), s2(t), and s3(t), where s1(t) and s2(t) are correlated with each other, and the correlation coefficient is defined as [22] (35)ρ≜Es1ts2∗tEs1t-ms1t2Es2t-ms2t2,where ms1(t)≜Es1(t) and ms2(t)≜Es2(t). The 2D DOAs of the three signals are set as (θ1=10∘, ϕ1=20∘), (θ2=30∘, ϕ2=35∘), and (θ3=40∘, ϕ3=150∘). The RMSEs of DOA estimation versus source correlation with respect to the second signal are shown in Figures 8 and 9, where the number of snapshots is N=100, M=9, and SNR=20dB.Figure 8
RMSE ofθ against correlation coefficient.Figure 9
RMSE ofϕ against correlation coefficient.It can be seen clearly form Figures8 and 9 that the accuracies of the RMSEs of all the three algorithms increase as ρ increases. This implies that the accuracies of all the three algorithms decrease when correlated source exists. However, the proposed method has a similar performance to the RD-MUSIC algorithm, and it performs closely to the standard 2D-MUSIC over the wide range ρ=0 to ρ=1. Although the RMSEs of the new method are a little bigger than those of 2D-MUSIC, the complexity of the proposed method is much lower than that of 2D-MUSIC. Therefore, the new estimator makes an efficient trade-off between estimation accuracy and computational complexity.


## 6. Conclusion

We have proposed a novel efficient NSRD-MUSIC algorithm in this paper for 2D direction-of-arrivals (DOAs) estimation. The new method exploits the specific geometries of URAs to estimate 2D DOAs with efficient 1D spectral search, which costs a significantly reduced computational complexity as compared to 2D-MUSIC. Simulations indicate that NSRD-MUSIC which requires no pair matching has a significantly improved accuracy as compared to ESPRIT.



---

*Source: 127621-2015-12-31.xml*