An improved direction finding algorithm based on toeplitz approximation.  
Jump to Full Text  
MedLine Citation:

PMID: 23296331 Owner: NLM Status: InDataReview 
Abstract/OtherAbstract:

In this paper, a novel direction of arrival (DOA) estimation algorithm called the Toeplitz fourth order cumulants multiple signal classification method (TFOCMUSIC) algorithm is proposed through combining a fast MUSIClike algorithm termed the modified fourth order cumulants MUSIC (MFOCMUSIC) algorithm and Toeplitz approximation. In the proposed algorithm, the redundant information in the cumulants is removed. Besides, the computational complexity is reduced due to the decreased dimension of the fourthorder cumulants matrix, which is equal to the number of the virtual array elements. That is, the effective array aperture of a physical array remains unchanged. However, due to finite sampling snapshots, there exists an estimation error of the reducedrank FOC matrix and thus the capacity of DOA estimation degrades. In order to improve the estimation performance, Toeplitz approximation is introduced to recover the Toeplitz structure of the reduceddimension FOC matrix just like the ideal one which has the Toeplitz structure possessing optimal estimated results. The theoretical formulas of the proposed algorithm are derived, and the simulations results are presented. From the simulations, in comparison with the MFOCMUSIC algorithm, it is concluded that the TFOCMUSIC algorithm yields an excellent performance in both spatiallywhite noise and in spatiallycolor noise environments. 
Authors:

Qing Wang; Hua Chen; Guohuang Zhao; Bin Chen; Pichao Wang 
Publication Detail:

Type: Journal Article Date: 20130107 
Journal Detail:

Title: Sensors (Basel, Switzerland) Volume: 13 ISSN: 14248220 ISO Abbreviation: Sensors (Basel) Publication Date: 2013 
Date Detail:

Created Date: 20130108 Completed Date:  Revised Date:  
Medline Journal Info:

Nlm Unique ID: 101204366 Medline TA: Sensors (Basel) Country: Switzerland 
Other Details:

Languages: eng Pagination: 74657 Citation Subset: IM 
Affiliation:

School of Electronic and Information Engineering, Tianjin University, Tianjin 300072, China. dkchenhua@tju.edu.cn. 
Export Citation:

APA/MLA Format Download EndNote Download BibTex 
MeSH Terms  
Descriptor/Qualifier:

Full Text  
Journal Information Journal ID (nlmta): Sensors (Basel) Journal ID (isoabbrev): Sensors (Basel) ISSN: 14248220 Publisher: Molecular Diversity Preservation International (MDPI) 
Article Information Download PDF © 2013 by the authors; licensee MDPI, Basel, Switzerland. License: Received Day: 19 Month: 11 Year: 2012 Revision Received Day: 29 Month: 12 Year: 2012 Accepted Day: 06 Month: 1 Year: 2013 collection publication date: Year: 2013 Electronic publication date: Day: 07 Month: 1 Year: 2013 Volume: 13 Issue: 1 First Page: 746 Last Page: 757 PubMed Id: 23296331 ID: 3574701 DOI: 10.3390/s130100746 Publisher Id: sensors1300746 
An Improved Direction Finding Algorithm Based on Toeplitz Approximation  
Qing Wang  
Hua Chen*  
Guohuang Zhao  
Bin Chen  
Pichao Wang  
School of Electronic and Information Engineering, Tianjin University, Tianjin 300072, China; EMails: wqelaine@tju.edu.cn (Q.W.); keyi1110@163.com (G.Z.); chenbintju@tju.edu.cn (B.C.); wangpichao@tju.edu.cn (P.W.) 

* Author to whom correspondence should be addressed; EMail: dkchenhua@tju.edu.cn; Tel.: +8613803065882; Fax: +862227405614. 
During the last few decades, DOA estimation, which has been widely applied in the fields of sonar, radar, wireless communication, aeronautics, etc. [^{1}], plays a significant role in array signal processing. Among various DOA estimation methods, the so called subspace approaches based upon the eigende composition of the sample covariance matrix possess very appealing features for narrowband case. The multiple signal classification (MUSIC) [^{2}] algorithm which pertains to the aforementioned subspace method can achieve favorable resolution when compared with conventional algorithms, for instance, Capon beam forming algorithm. However, MUSIC and its improved versions require the prior knowledge of the noise characteristics of the sensors [^{3}]. Moreover, the total number of signals impinging on the array must be less than the number of sensors [^{4}]. Therefore, these problems limit the applicability of the MUSIC algorithms to practical environments.
Conventional array processing techniques utilize only the second order statistics (SOSs) of the received signal, which may have suboptimal performance due to the transmitted signals, combining with additive Gaussian noise, are often nonGaussian in real applications, e.g., as in a communications system [^{5}]. In addition, the SOSs have the drawback of being sensitive to the type of the noise. Fortunately, the fourth order cumulants (FOC) have been shown to be promising in solving these problems, since it is possible to recover phase information with cumulants for nonGaussian processes. Furthermore, the FOC are asymptotically blind to the Gaussian process. Thus, it is not necessary to model or estimate the noise covariance, as long as the noise is Gaussian, which is a rational assumption in many practical situations. Because of these advantages, we can substitute FOC for SOC with MUSIC algorithms. The method proposed in [^{6}] is defined as the MUSIClike algorithm based on FOC, which is also called fourth order cumulants MUSIC (FOCMUSIC) algorithm in this paper. With FOC, the effective array aperture of a physical array can be extended, which makes the number of estimated signals greater than or equal to that of sensors possible.
But the conventional MUSIClike algorithms have high computational requirements as a result of the great number of redundant information contained in the FOC matrix as well as the rigorous requirements of sampling snapshots for the FOC matrix estimation. To mitigate these drawbacks, a fast MUSIClike algorithm (the MFOCMUSIC algorithm) is proposed to reduce the computational complexity effectively [^{7}]. On the other hand, the FOC matrix infinitely approaches the theoretical value when the number of the snapshots goes to infinity [^{8}]. However, because of the existence of the estimation error of the FOC matrix, the performance of the MFOCMUSIC algorithm cannot be asymptotically optimal. So, the proposed algorithm in [^{9}] successfully applies the Toeplitz approximate method to the cumulants domain, which mainly focuses on the amplitude and phase error model. In this paper, the MFOCMUSIC algorithm in conjunction with Toeplitz approximation, which is termed the TFOCMUSIC algorithm, is proposed. The emphasis of the paper is on the investigation of how the algorithm is impacted by sampling snapshots. Firstly, in the TFOCMUSIC algorithm, the reducedrank FOC matrix is obtained by removing the redundant information encompassed in the primary FOC matrix. Meanwhile, the effective aperture of the virtual array remains unchanged. Then, with applying the Toeplitz approximation, the Toeplitz structure of the reducedrank FOC matrix is recovered. And finally, by using the MUSIC algorithm, the direction of arrival signals can be estimated.
The rest of this paper is organized as follows. Section 2 introduces the system model and the MUSIClike algorithm. In Section 3, the TFOCMUSIC algorithm is described in detail. Section 4 presents comparative simulation results that show the effectiveness of the proposed algorithm. Finally, we conclude this paper in Section 5.
Throughout the paper, lowercase boldface italic letters denote vectors, uppercase boldface italic letters represent matrices, and lower and uppercase italic letters stand for scalars. The symbol * is used for conjugation operation, and the notations (x)^{T} and (x)^{H} represent transpose and conjugate transpose, respectively. We use E(x), cum(x) and ⊗ to indicate the expectation operator, the cumulants, and the Kronecker product, separately.
Assume that M farfield narrowband plane wave signals s_{l}(t), (l = 1, …, M) impinging on a uniform linear array (ULA) of N identical omnidirectional sensors with λ/2 interelement spacing, where λ is the wavelength of the carrier. We suppose that the source signals are stationary and mutually independent, and that the noises with variance σ^{2} are statistically independent to the signals as well.
Then, the signal received in time t at the ith sensor can be expressed as
(1)
xi(t)=∑l=1MSl(t)ai(θl)+ni(t),i=1,……,N 
(2)
ai(θl)=exp(jπisinθl) 
In matrix form, it becomes a(θ_{l}) = [a_{1}(θl), …, a_{N}(θ_{l})]^{T}.
Then, rewriting Equation (1) in matrix form, we obtain
(3)
X(t)=AS(t)+N(t) 
The MUSIC algorithm makes use of the covariance matrix of the data received by the sensor array, denoted by
(4)
R2=E[X(t)XH(t)]=ARsAH+σ2I 
For symmetrically distributed signals, their oddorder cumulants are usually zero. Therefore, evenorder cumulants are the main objects of investigation, in particular with the FOC. There exist various definitions about the FOC matrix. For zero mean stationary random process, the 4th order cumulants can be defined as [^{6}]
(5)
cum(k1,k2,k3∗,k4∗)=E(xk1(t)xk2(t)xk3∗(t)xk4∗(t))−E(xk1(t)xk3∗(t))E(xk2(t)xk4∗(t))−E(xk1(t)xk4∗(t))E(xk2(t)xk3∗(t))−E[xk1(t)xk2(t)]E[xk3∗(t)xk4∗(t)]−k1,k2,k3,k4∈[1,N] 
The 2qth order data statistics are arranged generally controls the geometry and the number of Virtual Sensors (VSs) of the Virtual Array (VA) and, thus, the number of sources that can be processed by a 2qth order method exploiting the algebraic structure of 2qth order circular cumulants matrix C_{2q,x}. Introduce g as an arbitrary integer (0 ≤ g ≤ q), for different arrangement of C_{2q,x}(g). To optimize the maximum number of VSs with respect to g, the optimal arrangement of the data statistics was solved in [^{10}] that g_{opt} = q/2 if q is even, and g_{opt} = (q + 1)/2 if q is odd. But In the particular case of a ULA of N identical sensors, it has been shown that all the considered arrangements of the data statistics are equivalent and give rise to VA with N2qg=q(N−1)+1VSs. Whereas for UCA, results differs, which was not discussed in this paper. If source signal is independent of each other, C_{4} can be written as Equation (6), which corresponds to the C_{2q,x}(g) matrix for the situation of q = 2 and g = 2 in [^{10},^{11}].
(6)
C4[(k1−1)N+k2,(k3−1)N+k4]=BCsBH 
(7)
Cs=diag(cum(s1(t),s1(t),s1∗(t)s1∗(t)),……,cum(sM(t),sM(t),sM∗(t),sM∗(t))) 
(8)
ϕ(θ)=1b(θ)HENENHb(θ) 
(9)
b(θ)=a(θ)⊗a(θ) 
As proven in [^{12}], for the MUSIClike algorithm, an array of arbitrary identical physical sensors can be extended to a maximum of N^{2} − N + 1 virtual ones. Specifically, the number of virtual sensors is showed in [^{12}] to be 2N − 1 with regard to ULA. In order to analyze the array effective aperture of ULA, we assume that there exist three real sensors, namely N = 3 in space and specialize Equation (9) as follows
(10)
b(θ)=[1,p,p2,p,p2,p3,p2,p3,p4]T 
(11)
a(θ)=[1,p,p2]T 
Comparing Equation (10) with (11), we can see that only two items are different implying that the effective array aperture is extended with 2N − 1 = 5 elements, and the remaining items of Equation (10) are redundant. With the increase of the sensors' number, b(θ) is highly redundant which leads to a heavy computational burden. Next, we will investigate the redundant elements in b(θ), and describe how to remove redundancy and to improve the computational efficiency.
The effective number of different sensors N2qg is smaller than the upperbound N_{max}[2q, g] for ULA [^{10}], which means redundancy in the virtual array can be removed using the reduceddimension method. But for UCA, N2qg is equal to N_{max} [2q, g] in the 4th order array processing method. i.e., N_{4}^{2} = N_{max}[4, 2] = N(N + 1)/2, for N is odd [^{10}]. So the proposed algorithm cannot reduce the computational complexity for UCA in reduceddimension method.
In this section, we describe the MFOCMUSIC algorithm combined with Toeplitz approximation in detail. To begin with, the MFOCMUSIC algorithm is described. From Equation (10), we know that there is a lot of redundancy in expanded steering vector b(θ). In general, for the Narray ULA, only from 1 to N and all kN(k = 2, …, N) items of the expanded steering vector b(θ) are valid for the MUSIClike algorithm, while others are redundant items. Owing to the steering vector of each element in accordance with the corresponding element, accordingly, C_{4} definitely exists a large number of duplicate values. The MFOCMUSIC algorithm is to remove the redundant information, at the same time, to extend the array aperture.
In light of the above analysis, it can be seen that C_{4} has 2N − 1 different elements, that is, the rows and columns number of C_{4} is 2N − 1. Next, we define a (2N − 1) × (2N − 1) dimension matrix denoted by R_{4}. Now let's take out the 1th to Nth and all kNth (k = 2, …, N) rows of C_{4} in sequence, and then store these rows in the 1th to (2N − 1)th row of the newly defined matrix R_{4}. The same operation is performed on the 1th to Nth and all kNth (k = 2, …, N) columns of C_{4} to obtain the 1th to (2N − 1)th columns of R_{4}.
Like in Equation (6), R_{4} has a similar mathematical expression as follows
(12)
R4=DCsDH 
In practical applications, we do not have access to true C_{4}. Instead, we utilize the estimated R̂_{4} in lieu of C_{4} from the received data by array measurements, subsequently, Ĉ_{4} which signifies the estimation value of R_{4} is in place of R_{4}, too. In order to obtain satisfactory results, a large number of sampling snapshots are required for cumulants domain processing. As is well known that the signal covariance matrix R_{2} of an ideal ULA is Toeplitz [^{13}], so do R_{4}. However, in the case of finite snapshots, the above desired properties cannot be preserved. To recover the Toeplitz property of R̂_{4}, the Toeplitz approximation, which was primarily presented for DOA estimation of coherent sources [^{14}], is employed to generate a Toeplitz matrix R̂_{4}_{T} from the biased matrix R̂_{4}. It is shown that the eigenstructure of R̂_{4}_{T} infinitely approaches that of R_{4}, as sampling snapshots gradually increase. And then the TFOCMUSIC algorithm takes advantage of R̂_{4}_{T} for eigendecomposition rather than R̂_{4} to get the signal and noise subspaces representing Û_{S} and Û_{N}, respectively.
Since the similar expression between R_{2} and R_{4}, we reconstruct a Toeplitz matrix R̂_{4}_{T} from R_{4} in the minimum metric distance sense by solving the following optimization problem [^{13}]:
(13)
minR4T∈ST‖R4T−R4‖ 
(14)
zˆh=(2N−1−h+1)−1∑p=12N−1−h+1rˆp(p+h−1) 
(15)
Rˆ4T=Toep(zˆ1,……zˆ2N−1) 
The procedure of the TFOCMUSIC algorithm is detailed as follows:
 Step 1 Estimate Ĉ_{4} from the received data by array measurements X(t) with Equations (5) and (6).
 Step 2 Take out the 1th to Nth and all kNth (k = 2, …, N) rows of Ĉ_{4} in order, and then store these rows in the 1th to 2N1th row of the R̂_{4} matrix.
 Step 3 Gain the columns of R̂_{4} via using its conjugate symmetry for reducing computation.
 Step 4 Apply Toeplitz approximation to R̂_{4} for R̂_{4}_{T} as Equations (14) and (15).
 Step 5 Remove the redundant items of the expanded steering vector b(θ), the rest items can be rewritten as a new vector d(θ) = [1, …, p^{2N}^{−}^{2}]^{T} according to the ascending order.
 Step 6 The estimate of DOAs of source directions can be attained by searching the peaks of redefined spatial spectrum p(θ), which can be expressed as
[Formula ID: FD16]
(16)P(θ)=1d(θ)HUNUNHd(θ)θ∈[−90°,90°]
According to the principle of the TFOCMUSIC algorithm, when compared with the MFOCMUSIC algorithm, it incurs 2(2N − 1) − 1 average operations, 2(2N − 1)^{2} − (2N − 1) additive operations and 2(2N − 1) − 1 conjugate operations. However, the TFOCMUSIC algorithm can estimate the DOA of more targets with less sensors, it can be considered that the calculation of the TFOCMUSIC algorithm is approximately in agreement with that of the MFOCMUSIC algorithm.
In this part, we evaluate the performance of the TFOCMUSIC algorithm with several experiments in spatiallywhite noise and in spatiallycolor noise environment, respectively. The FOCMUSIC, MFOCMUSIC and TFOCMUSIC algorithms are compared in terms of spatial spectrum, normalized probability of success, average maximum estimate deviation and average estimate variance of incoming signals with respect to variables such as angle θ, signaltonoise ratio (SNR) and sampling snapshots L. We defined three criteria, namely normalized probability of success (NPC), average maximum estimate deviation (AMED) and average estimate variance (AEV), to evaluate the performance. Define the event that satisfies max (θ̂_{i}−θi) < ε, i = 1,⋯M as “success”. Where ε equals 0.8 and 1.8 for comparison versus SNR and snapshot, respectively. The normalized probability of success equals the times of successes as follows:
(17)
NPC=times of“success”happensMC 
(18)
AMED=AveMC[max(θ^i−θi)]=∑j=1MCmax(θ^i−θi)MC,i=1,⋯M 
(19)
AEV=∑i=1Mvarθ^iM=∑j=1M{E(θ^i)2−[E(θ^i)]2}M,i=1,⋯M 
Spatial Spectrum versus Angle θ
Figure 1 exhibits the use of the FOCMUSIC, MFOCMUSIC and TFOCMUSIC algorithms to detect the bearings of three impinging sources in both spatiallywhite noise and spatiallycolor noise situations. Here, the SNR at each sensor is 10 dB, and L = 1,000. As depicted in Figure 1, the three sources have been successfully detected in abovementioned two types of noise by the three algorithms. However, the angular resolution of the TFOCMUSIC algorithm is much higher than the FOCMUSIC and MFOCMUSIC algorithms. The reason for the improvement of angular resolution with the TFOCMUSIC algorithm is that R̂_{4}_{T} achieved with Toeplitz approximate method is further close to the desired R_{4} than R̂_{4} in the same condition.
Normalized Probability of Success, Average Maximum Estimate Deviation and Average Estimate Variance versus SNR
The estimated performances of normalized probability of success, average maximum estimate deviation and average estimate variance are plotted in Figures 2–4 as a function of the SNR, respectively. Snapshots L are set to be 2,000, and 200 Monte Carlo's runs are carried out for estimators. As can be seen from three pictures, it is obvious that for low SNRs, the TFOCMUSIC algorithm outperforms the FOCMUSIC and MFOCMUSIC algorithms in all the three performances metrics. Moreover, as the SNR increases, the performance curves of each figure tend to become consistent by and large. But the TFOCMUSIC algorithm decreases the complexity by removing the matrix redundancy. The better behavior of the TFOCMUSIC algorithm is also determined by recovering the Toeplitz structure of R̂_{4} using Toeplitz approximation which improves the performance of DOA estimation.
Normalized Probability of Success, Average Maximum Estimate Deviation and Average Estimate Variance versus Snapshots L
Figures 5–7 show the DOA estimation performance with the FOCMUSIC, MFOCMUSIC and TFOCMUSIC algorithms in the same setting with SNR = 10 dB, 500 Monte Carlo's simulations setup. From the simulation results (Figures 5–7), it is clearly indicated that the curves obtained by the TFOCMUSIC algorithm are much better than those by the FOCMUSIC and the MFOCMUSIC algorithms either in spatiallywhite or spatiallycolor noise situation. And the three pictures' curves display sharp fluctuation for snapshots from 400 to 600 due to the small snapshots case, the estimate matrix R̂_{4} deviates from the ideal R_{4} much further.
In addition, the performance curves become stabilized with an increasing data length. Hence, we ascertain that the estimated performance becomes optimal, since the snapshots number goes to infinity. But in the convergence progress, the complexity of the TFOCMUSIC algorithm is obviously smaller than that of the FOCMUSIC algorithm, and the convergence speed of the TFOCMUSIC algorithm is much faster than that of the MFOCMUSIC algorithm. Complexity reducing benefit from the lower cumulants matrix rank dimension of the TFOCMUSIC algorithm compared to the FOCMUSIC algorithm. The cumulants matrix reconstructed using the Toeplitz approximate method is close to the desired R_{4} than the MFOCMUSIC algorithm in the same condition, which helps speed up the convergence.
To sum up, as can be noticed from Figures 1 to 7, compared with the MFOCMUSIC algorithm, the TFOCMUSIC algorithm behaves better in spatial spectrum estimation, normalized probability of success, average maximum estimate deviation and average estimate variance of incoming signals for both spatiallywhite noise and spatiallycolor noise situations. The modified Toeplitz structure of reducedrank R̂_{4}, namely, R̂_{4}_{T} contributes to the improvement of the performance of DOA estimation while yet maintaining property extending the effective array aperture of a physical array. Besides, the complexity increase is not obvious for a small array size.
A novel DOA estimation algorithm has been presented in this paper. Its main idea is to utilize the MFOCMUSIC algorithm in conjunction with Toeplitz approximation. In this way, the effective array aperture of a physical array can be extended that allows the number of estimated signals to be greater than or equal to that of sensors. Moreover, for nonGaussian sources, in contrast to the MFOCMUSIC algorithm, the proposed method has lower average maximum estimate deviation and average estimate variance, higher normalized probability of success and angular resolution. And the threshold of snapshots is less than that of the MFOCMUSIC algorithm to some extent. In addition, the computation of the TFOCMUSIC algorithm is approximately consistent with that of the MFOCMUSIC algorithm, while obviously smaller than the FOCMUSIC algorithm due to estimating DOA of more targets with less sensors. Simulation results show that the proposed method is more effective and efficient than the MFOCMUSIC algorithm in DOA estimation, both in spatiallywhite noise and spatiallycolor noise situations.
This work has been financially supported by the National Natural Science Foundation of China (Grant No. 61101223), the 863 program (Grant No. 2011AA010201), and the Doctoral Foundation from Ministry of Education of China (Grant No. 20110032120087 and 20110032110029).
References
1..  Krim H.,Viberg M.. Two decades of array signal processing research: The parametric approachIEEE Signal Process. Mag.Year: 1996136794 
2..  Schmidt R.O.. Multiple emitter location and signal parameter estimationIEEE Trans. Antenn. Propag.Year: 198634276280 
3..  Schell S.V.,Calabretta R.A.,Gardner W.A.,Agee B.G.. Cyclic MUSIC Algorithms for SignalSelective Direction EstimationProceedings of International Conference on Acoustics, Speech, and Signal ProcessingGlasgow, UK23–26 May 1989 
4..  Shan Z.,Yum T.P.. A conjugate augmented approach to directionofarrival estimationIEEE Trans. Signal Process.Year: 20055341044109 
5..  Dogan M.C.,Mendel J.M.. Applications of cumulants to array processing I: Aperture extension and array calibrationIEEE Trans. Signal Process.Year: 19954312001216 
6..  Porat B.,Friedlander B.. Direction finding algorithms based on highorder statisticsIEEE Trans. Signal Process.Year: 19913920162024 
7..  Tang J.H.,Si X.C.,Chu P.. Improved MUSIC algorithm based on fourthorder cumulantsSyst. Eng. Electron.Year: 201032256259 
8..  Dogan M.C.,Mendel J.M.. Cumulantbased blind optimum beam formingIEEE Trans. Aero. Electron. Syst.Year: 199430722741 
9..  Wu H.,Bao Z.. Robustness of DOA estimation in cumulant domainActa Electron. Sin.Year: 1997252529 
10..  Chevalier P.,Albera L.,Ferreol A.,Comon P.. On the virtual array concept for higher order array processingIEEE Trans. Signal Process.Year: 20055312541271 
11..  Chevalier P.,Ferreol A.,Albera L.. High resolution direction finding from higher order statistics: The 2qMUSIC algorithmIEEE Trans. Signal Process.Year: 20065429862997 
12..  Chevalier P.,Ferreol A.. On the virtual array concept for the fourthorder direction finding problemIEEE Trans. Signal Process.Year: 19994725922595 
13..  Chen Y.M.,Lee J.H.,Yeh C.C.. Bearing estimation without calibration for randomly perturbed arraysIEEE Trans. Signal Process.Year: 199139194197 
14..  Kung S.,Lo C.,Foka R.. A Toeplitz Approximation Approach to Coherent Source Direction FindingProceedings of International Conference on Acoustics, Speech, and Signal ProcessingTokyo, Japan7–11 April 1986 
Article Categories:
Keywords: DOA estimation, fourth order cumulants, MUSIClike, Toeplitz approximation, spatiallywhite noise, spatiallycolor noise. 
Previous Document: Detection of Aeromonas hydrophila in Liquid Media by Volatile Production Similarity Patterns, Using ...
Next Document: A facile electrochemical sensor for nonylphenol determination based on the enhancement effect of ce...