Computationally Efficient 2D-DOA Estimation for Uniform Planar Arrays:RD-ROOT-MUSIC Algorithm

，，，

1.Key Laboratory of Dynamic Cognitive System of Electromagnetic Spectrum Space，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，P.R.China；

2.College of Electronic and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，P.R.China

Abstract:The problem of two-dimensional direction of arrival（2D-DOA）estimation for uniform planar arrays（UPAs）is investigated by employing the reduced-dimensional（RD）polynomial root finding technique and 2D multiple signal classification（2D-MUSIC）algorithm.Specifically，based on the relationship between the noise subspace and steering vectors，we first construct 2D root polynomial for 2D-DOA estimates and then prove that the 2D polynomial function has infinitely many solutions.In particular，we propose a computationally efficient algorithm，termed RD-ROOT-MUSIC algorithm，to obtain the true solutions corresponding to targets by RD technique，where the 2D root-finding problem is substituted by two one-dimensional（1D）root-finding operations.Finally，accurate 2DDOA estimates can be obtained by a sample pairing approach.In addition，numerical simulation results are given to corroborate the advantages of the proposed algorithm.

Key words：uniform planar array（UPA）；direction of arrival（DOA）estimation；RD-ROOT-MUSIC algorithm

0 Introduction

In the past few decades，two-dimensional direction of arrival（2D-DOA）estimation has drawn considerable attention and has been utilized in many fields such as astronomy，wireless communications，and radar systems［1-3］.Most of the existing research mainly focus on structures of 2D arrays such as uniform planar array（UPA）［4-6］，L-shaped array［7-8］，uniform circular array（UCA）［9］and two parallel uniform linear arrays［10］.For these 2D arrays，the spacing of adjacent sensors should be no larger than half wavelength to eliminate phase ambiguity problem.

Conventional 2D-DOA methods mainly include two categories that one is based on spectrum peak search［11-18］，and the other exploits the rotation invariance algorithm［9，19-21］.In Ref.［11］，the traditional 2D multiple signal classification（2D-MUSIC）algorithm is employed to UPA，where the well-performed DOA estimates can be obtained with expensive computational complexity caused by the total spectral search（TSS）.Ref［.17］combined the reduced-dimensional MUSIC（RD-MUSIC）method with multiple-input-multiple-out（MIMO）radar to complete 2D-DOA estimation，to further reduce the computational complexity.The rotation invariance algorithm can directly calculate the DOA estimates and avoid spectral peak searching，but cannot achieve as good DOA estimates as the algorithms based on spectral peak searching.Ref.［18］proposed one-dimensional（1D）partial spectral search approach for coprime planar arrays，which achieved enhanced DOA performance with muchlower computational cost as compared with 2D-MUSIC algorithm，but it still performed peaks searching on spectrum function.To achieve a better tradeoff between computational complexity and DOA estimation performance，scholars have proposed some methods based on MUSIC algorithm to reduce computational complexity by utilizing polynomial root finding technique［22-24］.Ref.［23］proposed a polynomial rooting algorithm based on L-shaped array，which failed to make full use of 2D array information.In Refs［.24-25］，the initial 1D roots were calculated first and then were used to obtain all the DOA estimates based on the spectrum function.However，the 2D-DOA estimation performance of the methods degrades at low signal-to-noise ratio（SNR）because bad initial DOA estimates exist in this case.

Considering the disadvantages mentioned above in conventional methods，we propose a computationally efficient algorithm based on RD polynomial root finding technique for UPA termed RDROOT-MUSIC algorithm.Based on the 2D-MUSIC spectrum function，we consider 2D-ROOTMUSIC polynomial firstly and explore to find two paired solutions corresponding to targets directly.Subsequently，we prove that 2D polynomial contains infinitely many solutions，and it is impossible for us to obtain the solution to a bivariate higher-order equation by once polynomial root finding without other qualifications.According to 2D-ROOTMUSIC polynomial，we construct two 1D root polynomials to obtain 2D-DOA estimates corresponding to targets from infinitely many solutions by RD root finding technique.Furthermore，we also exploit the feasibility and effectiveness of the RD process.Although the proposed algorithm requires an additional parameter pairing procedure，it only needs extremely low complexity.Compared with RD-MUSIC algorithm and 2D-MUSIC algorithm，the proposed algorithm can get roughly the same 2D-DOA estimation accuracy，but the computational complexity is much lower.Numerical simulations corroborate the effectiveness and priority of the proposed algorithm.

Specially，the main contributions of this paper are summarized as follows：

（1）We devise the 2D-DOA estimation problem for UPA as a polynomial rooting problem，to achieve high accuracy DOA estimates with a much lower computational cost.

（2）We prove that 2D-ROOT-MUSIC polynomial contains infinitely many solutions.

（3）We propose a computationally efficient algorithm termed RD-ROOT-MUSIC algorithm，which exploits the feasibility and effectiveness of the RD polynomial root finding process.

Notations：Bold lower-case and upper-case characters are used to represent the vectors and matrices，respectively.(·)T，(·)H，(·)-1and(·)*represent transpose，conjugate transpose，inverse and conjugate operations，respectively.⊙and?stand for the Khatri-Rao product and Kronecker product，respectively.I Mis theM×Midentity matrix.angle(·)stands for the phase operator and det(·)denotes the determinant of the matrix.

1 Data Model

The UPA structure is shown in Fig.1，which containsM×Nsensors.The inter-element spacing isd=λ2，whereλdenotes the wavelength.

Assume there areK(K＜MN)narrowband farfield uncorrelated sources impinging on the UPA from 2D-DOA elevation angles (θk，φk)，k=1，2，…，K，whereθkandφkare the elevation and azimuth angles of thekth sources(θk∈[ 0，π2]，φk∈[0，π])，respectively.

The received signals can be expressed as［11］

whereX=[x(1)，x(2)，…，x(L)]andLrepresents the number of snapshots，S=[s1，s2，…，s K]Tis the source signal matrix ands k=[sk(1)，sk(2)，…，sk(L)]，andsk(l)=βkej2πfk twith the Doppler frequencyfkand the amplitudeβk.N∈CMN×Lis the additive white Gaussian noise matrix with zero mean and varianceσ2.A∈CMN×Kis the steering matrix of the UPA and

wherea x(θk，φk)anda y(θk，φk)are steering vectors ofA.They can be represented by

Based on the eigenvalue decomposition（EVD），can be decomposed as

whereEsis formed by the eigenvectors corresponding to the maximumKeigenvalues，andEnis composed of the rest eigenvectors.DsandDnare diagonal matrices.The diagonal elements ofDsare made up of the largestKeigenvalues，and the diagonal elements ofDnare composed of other eigenvalues.

Remar k 1In this paper，it is assumed thatKis the prior information which can be estimated by the methods in Refs［.26-27］.

The covariance matrix can be calculated withLsnapshots by

2 The Proposed Algorithm

In this section，we first construct 2D-ROOTMUSIC polynomial and prove that it contains infinitely many solutions，then we apply the RD polynomial root finding process to get two 1D polynomials.Besides，we exploit the feasibility and effectiveness of the RD process.Accurate 2D-DOA estimates corresponding to targets can be obtained by the proposed algorithm.

2.1 2D-MUSIC algorithm

The spectrum function of UPA can be expressed as［11］

wherea y(θ，φ)=[1，ej2πdsinφsinθλ，…，ej2π(M-1)dsinφsinθλ]T，anda x(θ,φ)=[1,ej2πdcosφsinθλ,…,ej2π(N-1)dcosφsinθλ]T.

In Ref.［12］，the authors performed 2D partial spectral search（PSS）on Eq（.7）to obtain 2DDOA estimates，which requires a time-consuming 2D spectral search.In Ref.［14］，Zhang et al.utilized RD technique，but it still needed 1D spectral search.We utilize polynomial root finding process instead of spectral peak search，which greatly reduces the computational cost.

2.2 2D-ROOT-MUSIC polynomial

Define

then，the steering vectors can be rewritten as

2D-ROOT-MUSIC polynomial can be expressed as

Lemma 1The UPA structure is shown in Fig.1.By performing EVD on covariance matrix，2D-ROOT-MUSIC polynomial corresponding to the UPA can be expressed as Eq.（11），which contains infinitely many solutions.

ProofSee Appendix A.

According to Lemma 1，it is not feasible to obtain the paireduandvdirectly from 2D-ROOTMUSIC polynomial because of infinitely many solutions.We use RD polynomial root finding technique to solve this problem.

2.3 RD polynomial root finding process

According to Eq.（11），V(u，v)can be reconstructed as［14，17］

or

where

Basically，the above states derivations covert DOA estimation into polynomial root finding with Eq.（11），if ej2πduλdoes not correspond to one target and if［24-25］

Considering about the noise with non-zero value，the matrixEnis invertible，and the determinant is not equal to zero.

Eq（.16）means that det{Q(u)}is non-zero polynomial.Obviously，Q(u)is a factor ofV(u，v).SinceQ(u)contains only the variableu，ifutakes the value that satisfies

the roots of Eq（.17）must containucorresponding to targets.Eq（.17）also means

The analysis of the variablevis similar.Then the problem of obtaininguandvcorresponding to targets from infinitely many solutions in Eq（.11）can be converted into two 1D polynomials root finding problems.Eqs.（12）and（13）can be converted into

Define

The steering vectors can be rewritten as

Since the degree of det{Q(z1)} and det{Q(z2)} are even， we can take roots，…，…of Eq（.24）with the largestKamplitudes in the unit circle to obtain estimates of，and take roots，…，，…，of Eq.（25）with the largestKamplitudes in the unit circle to obtain estimates of.

2.4 Pairing and 2D-DOA estimation

The estimates ofandare separated，so it is necessary to pairandto complete 2D-DOA estimation.Construct cost function(k=1，…，K)

wherea y()anda x()represent steering vectors reconstructed byand，respectively.

It is obvious that the total number ofV k，iisK2.Then for eachk，we can calculateV k，i(1≤i≤K)to select the minimum value and return correspondingiintoi'.2D-DOA estimates can be calculated by

2.5 Detailed steps of the proposed algorithm

The major steps of the proposed algorithm to obtain 2D-DOA estimates for the UPA are given as follows.

Step 1Compute the covariance matrixand perform EVD to obtain noise subspaceEn.

Step 2ReconstructV(u，v) according to Eq（.11）.

Step 3Perform RD process onV(u，v)to get Eqs（.24）and（25）.

Step 4Calculateandaccording to Eqs.（26）and（27）.

Step 5Complete pairing procedure and obtain the 2D DOA estimation of targets according to Eqs（.29）and（30）.

3 Performance Analysis

3.1 Complexity analysis

We analyze the computational complexity of the proposed algorithm and compare it with the 2DESPRIT algorithm［9］，2D-MUSIC algorithm［11］，and RD-MUSIC algorithm［17］.For the proposed algorithm，calculating the covariance matrix needsO{(MN)2L}，eigenvalue decomposition requiresO{(MN)3}， polynomial root finding costsO{(2N(M-1))3+(2M(N-1))3}and the pairing process requiresO{K2(MN+1)(MN-K)}，so the total computational complexity of the proposed algorithm is

The computational complexities of 2D-ESPRIT with UCA，2D-MUSIC with passive array and RD-MUSIC with MIMO radar are given in Refs.［9］，［11］and［17］，respectively.We extend them to the complexities of UPA for comparison.Both algorithms requireO{(MN)2L+(MN)3}to obtain the covariance matrix and perform eigenvalue decomposition.The peak search of 2D-MUSIC and RD-MUSIC costsO{(MN+1)(MN-K)}andO{n2K(M2N+M2)(MN-K)}，respectively，wheren1=90°/Δandn2=2°/Δrepresent the search times，and the peak search interval isΔ=0.01°.For 2D-ESPRIT algorithm，further accurate estimation needsO{2K2(M-1)N+6K3+2K2(N-1)M}.The computational complexity of different algorithms mentioned above is summarized in Table 1.Besides，Fig.2 shows the computational complexity comparison of different algorithms versus differentN，whereM=6，K=2，L=500.The complexity comparison versus snapshot is depicted in Fig.3，whereM=6，N=6，K=2.It is observed from Figs.2 and 3 that the proposed algorithm outperforms the 2D-MUSIC and RD-MUSIC algorithms in computational complexity，and its computational complexity is approximately as low as the 2D-ESPRIT algorithm，proving the computational efficiency of the proposed algorithm.

Table 1 Complexity comparison of different methods

Fig.2 Computational complexities of different methods versus different N

Fig.3 Computational complexities of different methods versus different snapshots

3.2 Cr amer-Rao bound

The Cramer-Rao bound（CRB）represents a lower bound to the error variance of parameter estimator.We give the derivation of CRB for UPA to evaluate the 2D-DOA estimation performance as follows

According to Ref.［28］，the CRB of UPA can be given by

AH.HereLrepresents the number of snapshots，a kthekth column ofA，andσ2the variance of the received noise.

3.3 Advantages

Based on the above discussions，the proposed algorithm has the following advantages.

（1）The proposed algorithm converts 2D polynomial into 1D polynomials，and does not require spectrum search，thus reducing the computational complexity significantly.

（2）The complexity of the proposed algorithm is approximately as low as the 2D-ESPRIT algorithm，which is much lower than the 2D-MUSIC and RD-MUSIC algorithms.

（3）The 2D-DOA estimation accuracy of proposed algorithm is significantly better than 2D-PM and 2D-ESPRIT algorithms，and is almost the same as 2D-MUSIC and RD-MUSIC algorithms.

（4）The proposed algorithm can be effectively used for 2D-DOA estimation with high accuracy 2DDOA estimation and is also attractive in massive MIMO radar system.

4 Simulation Results

In this section，we employ Monte Carlo simulation to simulate the proposed algorithm.The number of Monte Carlo simulation is 500.Assume that the incident angles are (θ1，φ1)=(20°，30°)(θ2，φ2)=(40°，50°) of two unrelated sources(i.e.K=2).Inter-element spacingdequals half wavelength.We can define the root mean square error（RMSE）of the 2D-DOA estimation as

whereφkandθkrepresent the true azimuth and elevation of thekth target，respectively.φ^k，iandθ^k，iare estimated value ofφkandθkin theith Monte Carlo simulation，respectively.

4.1 Scatter figures

Fig.4 shows the scatter figures of the proposed algorithm，whereM=6 andN=6.The SNR of Fig.4（a）and Fig.4（b）are-10 dB and 10 dB，respectively.It is obviously shown that the proposed algorithm can obtain paired azimuth and elevation effectively.

Fig.4 Scatter figures of the proposed algorithm

4.2 RM SE performance comparison results versus snapshot

Fig.5 gives the comparison results of RMSE performance for UPA versus snapshot，whereM=6，N=6.An increased number of snapshots means more sampling data.As the number of snapshots increases，it is illustrated clearly that the 2D-DOA estimation performance gets better in Fig.5.

Fig.5 RMSE performance versus snapshot

4.3 RMSE performance comparison results versus sensor

Fig.6 depicts the comparison results of RMSE performance versus sensorsMandN，whereL=200.An increased number of sensors means more diversity gain received by UPA.Fig.6 indicates that the 2D-DOA estimation performance is enhanced as the number of sensors increases.

Fig.6 RMSE performance versus sensors

4.4 2D-DOA performance comparison results of different algor ithms

We investigate 2D-DOA estimation performance comparison results of the proposed algorithm，2D-MUSIC algorithm，2D-PM algorithm［21］，2D RD-MUSIC and 2D-ESPRIT algorithms for UPA，whereM=6，N=6，SNR=10 d B in Fig.7（a）andM=6，N=6，L=200 in Fig.7（b）.The range of spectrum searching for 2DMUSIC is(0°，90°)，and searching interval isΔ=0.01°.As depicted in Fig.7，the performance of the proposed algorithm is almost identical to the 2DMUSIC algorithm and RD-MUSIC algorithm.Compared with the 2D-ESPRIT and 2D-PM algorithms，the proposed algorithm performs significantly better，verifying its effectiveness.

Fig.7 Comparison of RMSE performance of different algorithms

5 Conclusions

Based on RD polynomial rooting technique and 2D-MUSIC algorithm，a novel computationally efficient algorithm with improved DOA estimation performance is proposed in this paper.We first take 2D ROOT-MUSIC polynomial into consideration，which contains infinitely many solutions，and it is difficult to get paired solutions directly.For further，a novel method termed RD-ROOT-MUSIC algorithm with UPA is proposed to solve this problem.It converts 2D polynomial into two 1D polynomi-als，then the computational complexity and root finding difficulty can be reduced，effectively.In addition，a better trade-off between computational complexity and 2D-DOA performance is achieved，as compared with other existing methods.Numerical simulations validate the effectiveness and efficiency of the proposed algorithm.

Appendix A

Fundamental theorem of algebra：Every non-constant single-variable polynomial with complex coefficients has at least one complex root.

According to Eqs（.11—13），2D-ROOT-MUSIC polynomial can be rewritten as

where

Expand the coefficient ofV(z1，z2)

wherea1(z2)，…，a N(z2)are all polynomials ofz2andCis a constant.

According to Eq.（16），polynomial coefficients ofa1(z2)，…，a N(z2)are not all zero.Givez2an arbitrary value that satisfies

then Eq（.A 4）is converted into a univariate equation with only the variablez1.The value ofz2is an arbitrary complex number that satisfies the value range.There are infinitely manyz2values and eachz2corresponds to at least onez1.According to Fundamental theorem of algebra，Eq（.11）contains infinitely many solutions in the complex number range.

AcknowledgementsThiswork wassupported by the National Natural Science Foundation of China（Nos.61631020，61971218，61601167，61371169）.

AuthorMr.YE Changbo received his B.S.degree in communication engineering from Nanjing University of Aeronautics and Astronautics（NUAA），Nanjing，China，in 2019.He is currently pursuing the M.S.degree in communication and information systems with College of Electronic and Information Engineering，NUAA.His research interests include spare array processing and communication signal processing.

Author contributionsMr.YE Changbo designed the study，complied the models，simulated the algorithms and wrote the manuscript.Mr.ZHU Beizuo contributed to data，model components for the UPA and the discussion of the study.Mr.LI Baobao participated in the part of the algorithm simulation work. Prof. ZHANG Xiaofei contributed to the data analysis and the background of this study.All authors commented on the manuscript draft and approved the submission.

Competing inter estsT he authors declare no competing interests.