Fast Algorithm for DOA Estimation with Partial Covariance Matrix and without Eigendecomposition

doi:10.4236/jsip.2011.24037

Paper Menu >>

Journal Menu >>

Journal of Signal and Information Processing, 2011, 2, 266-269

doi:10.4236/jsip.2011.24037 Published Online November 2011 (http://www.SciRP.org/journal/jsip)

Fast Algorithm for DOA Estimation with Partial

Covariance Matrix and without

Eigendecomposition

Jianfeng Chen1, Yuntao Wu2*, Hui Cao2, Hai Wang2

1The 54th Institute of China Electronics Technology Group Corporation, Shijiazhuang, China; 2Key Laboratory of Intelligent Robot

in Hubei Province, Wuhan Institute of Technology, Wuhan, China.

Email: *[email protected]

Received July 17th, 2011; revised September 10th, 2011; accepted September 18th, 2011.

ABSTRACT

A fast algorithm for DOA estim ation without eigend ecomposition is proposed. Unlike th e availab le propagation method

(PM), the proposed method need only use partial cross-correlation of array output data, and hence the computational

complexity is further reduced. Moreover, the proposed method is suitable for the case of spatially nonuniform colored

noise. Simulation results show the performance of the proposed method is comparable to those of the existing PM

method and the standa rd MUSIC method.

Keywords: Fast Algorithm, DOA Estimation, Subspace-Based Method

1. Introduction

DOA estimation of spatial signal source with an array of

sensors has been an active research problem in array sig-

nal processing due to its wide applications in radar, sonar

and so on. Many classical algorithms have been devel-

oped in the past thirties years [1-3], in particular, a class

of subspace-based methods such as MUSIC [1], Root-

MUSIC [2], and ESPRIT [3] are drawn more attractive

due to its higher resolution performance but without mul-

tiple-dimension search computation. However, most of

the subspace-based methods are required to compute the

eigendecomposition of covariance matrix of array output

data in order to obtain the so-called signal subspace or

noise subspace, which its application is limited in case of

larger number of array sensors. To avoid the computa-

tional load of the eigendecomposition of covariance ma-

trix, in recent years, some fast algorithms for DOA esti-

mation have been proposed for certain condition in the

literature [4-7]. In particular, the propagation method (PM)

[6,7] without eigendecomposition has been discussed due

to lower computational load. However, the available PM

method need use the whole covariance of array output

data to obtain the propagation operator, therefore, the

PM-based algorithm is only suitable to the presence of

white Gaussian noise, and its performance will be de-

graded in spatial nonuniform colored noise [8].

In this paper, we present a modified PM algorithm for

DOA estimation with an ULA, a different computation

method for the propagation operator is given, which is

only obtained by the partially cross-correlation of array

output data. As a result, the proposed algorithm is com-

putationally simpler than the available PM method [6].

Moreover, the proposed algorithm is suitable for the case

of spatially nonuniform colored noise due to using the

off-diagonal elements of array covariance matrix.

2. Proposed Method

The template is used to format your paper and style the

text. All margins, column widths, line spaces, and text

fonts are prescribed; please do not alter them. You may

note peculiarities. For example, the head margin in this

template measures proportionately more than is custom-

ary. This measurement and others are deliberate, using

specifications that anticipate your paper as one part of the

entire proceedings, and not as an independent document.

Please do not revise any of the current designations.

Let an uniform linear array of N sensors receive P

narrow band signals impinging from the sources with

unknown spatial DOA’s





1,,



. The sensor array

outputs can be expressed as:













,1,2,,tttt



xAsn L (1)

Fast Algorithm for DOA Estimation with Partial Covariance Matrix and without Eigendecomposition267



where and

denote the received

array data vector and the array manifold matrix, respec-

tively. and

stand for the source wave-

form vector and sensor noise vector.

 

1,, T

txt xt



x

 

,,,

 

 



Aaa a

 

1,, T

tst st



s

 

1,, T

tnt nt







 



1,exp2 πdsin, ,

exp2π1dsin













a

is the steering vector and denotes the transposition

of a matrix. The sensors noise is assumed to be a zero

mean spatially and temporally white Gaussian process.





The following assumptions are made in the subsequent

developments:

(A1) The number of sources P is known a priori and the

number of sensors satisfies N > 2P.

(A2) The set of P steering vectors is linearly independent

and the P signal sources are statistically independent of

each other.

Under the assumption of N > 2P, the array manifold

matrix A can be partitioned as follows:

123

,, T

TTT





AAAA





(2)

where i, i=1,2,3 is a matrix with dimension P × P, P ×

P, (N – 2P) × P, respectively.

Based on the above partition of A and using Equation

(1), the following partially cross-correlation matrices of

the array output are defined as:

 







121 2

1:,:1 :2,:

Et PtPP







Rx xAR



A

(3)

 



 

313 1

21:,:1:,:

Et PNtP



 



Rxx AR





(4)

 





 





21:,: 1:2,:

Et PNtPP



 





Rx x

AR A





(5)

where takes the i-th to j-th row of

 

:,:tijx





tx,





denotes the Hermitian transpose and









ss Et





Rs 



is the source signal covariance matrix.

Under the assumption of (A2), both

s and i,

i = 1,2 are invertible matrices, therefore, the following

equation holds:

R A



32121 32211 3

ss ss





RRA ARAARAA A

1



(6)

Similarly, the following equation can also be obtained:

31 21 23

RRAA

(7)

Combines Equation (6) and Equation (7) and yields:

3212 13121 23



RRA RRAA (8)

Equivalently, the above equation can be written as:

32 1231 212

2NP











RRRRIA0

(9)

where 2

P

is an identical matrix with dimension N –

2P and

P

a zero matrix, respectively.

Let 11

32 1231 212

2NP















QRRRRI and we have



QA 0 (10)

which implies that the columns of

Q form a basis of

the null space of A, i.e.,







1, 2,,

HkkP



Qa 0

Using the estimated matrix from the finite array

output data in real application, similar to the MUSIC-

based method, we may form the following spatial spec-

trum function and obtain the estimates of

(1,2,,

kk}P





 from P spectrum peaks:

 

ˆH



Qa (11)

where











1,exp2πdsin, ,

exp2π1dsin













a

Alternately, using the Root-MUSIC-based method [2]

to get the estimation value of k



directly.

It is worthy to note that the estimation of need not

any eigendecomposition, and the noise information is not

involved in , therefore, the proposed method can be

used in the case of spatial non-uniform noise or spatial

band limited noise [8].

Regarding major computational complexity, the num-

ber of multiplications for calculating includes P(N -

P)L in the cross-correlation computation in Equations

(3)-(4) and O(P3) for the inversion of 12 in Equations

(6)-(7), respectively, while the MUSIC method [1] in-

volves N2L for covariance matrix computation and O(N3)

for the eigenvalue decomposition of the resultant covari-

ance matrix. On the other hand, the number of multipli-

cations for computing the propagation operator in

the available PM method [6] is NPL + O(P3). Apparently,

the computational complexity of the proposed algorithm

is lower than those of the MUSIC method and the pro-

pagation method.

3. Simulation Results

In the first simulation, the experiments are performed

with an uniform linear array (ULA) with N = 10 sensors

Fast Algorithm for DOA Estimation with Partial Covariance Matrix and without Eigendecomposition

268

and half-wavelength inter-element spacing. Two equally

powered narrow-band sources with DOA’s 17







and 2 impinge on the array and the two sources

are statistically independent of each other. Let L = 100

and the average results for 200 independent runs are used

to evaluate the estimation performance of different meth-

ods.





Figures 1-2 show the RMSEs (root-mean-square error)

for DOA estimation versus different SNR conditions.

The results using the conventional MUSIC algorithm [1],

the Standard ESPRIT method [3] and the available or-

thonormalisation PM (OPM) [7] method are also in-

cluded to contrast the performance of the proposed algo-

rithm. It is seen that the estimation accuracy of the pro-

posed method is comparable to those of the subspace-

based MUSIC method, ESPRIT and OPM method at all

the SNRs.

In the second experiment, we assume









,5,



6 and other parameters is same as the

above experiment, however, the spatially nonuniform

independent sensor noise has the following covariance

matrix:





2diag1,1.2, 4,12,11, 3, 0.4,10, 2



Q.

The definition of signal-noise-ratio (SNR) is the same

as that in [8]. The estimation results of the proposed

method for 10 independent runs in the case of SNR =

5dB are ploted in Figure 3. It is seen that the proposed

method can resolve accurately two closely spatial sources

in the presence of spatially nonuniform noise.

4. Conclusions

A computationally efficient algorithm for DOA estimation

with an uniform linear array has been presented. The par-

tial cross-correlation of array outputs is utilized to compute

the propagation operator, and hence the proposed method

is suitable to the case of spatially non-uniform noise. Fi-

nally, it is shown that the estimation performance of the

Figure 1. RMSEs of θ1 versus SNR.

Figure 2. RMSEs of θ2 versus SNR.

Figure 3. Spectrum of proposed method in spatially non-

uniform colored noise.

proposed algorithm is comparable to those of the available

PM method as well the conventional MUSIC method at

sufficiently higher SNR conditions.

5. Acknowledgements

The work described in this paper was jointly supported

by a grant from the National Natural Science Foundation

of China (Project No. 60802046) and the Research Plan

Project of Hubei Provincial Department of Education

(No. Q20091501).

REFERENCES

[1] R. O. Schmidt, “Multiple Emitter Location and Signal

Parameter Estimation,” IEEE Transactions on Antennas

and Propagation, Vol. 34, No. 3, 1986, pp. 276-280.

doi:10.1109/TAP.1986.1143830

[2] B. D. Rao and K. V. S. Hari, “Performance Analysis of

Root-Music,” IEEE Transactions on Acoustics, Speech

and Signal Processing, Vol. 37, No. 12, 1989, pp. 1939-

Fast Algorithm for DOA Estimation with Partial Covariance Matrix and without Eigendecomposition

269

1949. doi:10.1109/29.45540

[3] R. Roy and T. Kailath, “ESPRIT-Estimation of Signal

Parameters via Rotational Invariance Techniques,” IEEE

Transactions on Acoustics, Speech and Signal Processing,

Vol. 37, No. 17, 1989, pp. 984-995.

doi:10.1109/29.32276

[4] J. Xin and A. Sano, “Computationally Efficient Subspace

Based Method for Direction of Arrival Estimation with-

out Eigendecomposition,” IEEE Transactions on Signal

Processing, Vol. 52, No. 4, 2004, pp. 876-893.

doi:10.1109/TSP.2004.823469

[5] J. F. Gu, P. Wei and H. M. Tai, “Fast Direction-of-Arrival

Estimation with Known Waveforms and Linear Opera-

tors,” IET Signal Processing, Vol. 2, No. 1, 2008, pp. 27-

36. doi:10.1049/iet-spr:20070066

[6] S. Marcos, A. Marsal and M. Benidir, “The Propagator

Method for Source Bearing Estimation,” Signal Process-

ing, Vol. 42, No. 2, 1995, pp. 121-138.

doi:10.1016/0165-1684(94)00122-G

[7] J. Munier and G. Y. Delisle, “Spatial Analysis Using New

Properties of the Cross-Spectral Matrix,” IEEE Transac-

tions on Signal Processing, Vol. 39, No. 3, 1991, pp. 746-

749. doi:10.1109/78.80863

[8] Y. T. Wu, C. H. Hou, G. S. Liao and Q. H. Guo, “Direc-

tion of Arrival Estimation in the Presence of Unknown

Nonuniform Noise Fields,” IEEE Journal of Oceanic En-

gineering, Vol. 31, No. 2, 2006, pp. 504-510.

doi:10.1109/JOE.2006.875270