3.14.2.1 Wave propagation

The physics of propagating waves is governed by the wave equation for medium of interest. The homogeneous wave equation for a general scalar field at time instant t and location is given by

(14.1)

where the parameter c represents the propagation velocity. can be an electric density field in electromagnetics or acoustic pressure in acoustic waves.

A solution of special interest to (14.1) takes a complex exponential form:

(14.2)

where is the temporal frequency and is the wave number vector. Here is considered as the spatial frequency of this mono-chromatic wave. Inserting (14.2) into (14.1), one can readily see how temporal frequency and the spatial frequency k are related:

(14.3)

Replacing the propagation velocity with in (14.3) where is the wavelength, the magnitude of the wave number vector is given by .

The elementary wave (14.2) also represents a propagating wave

(14.4)

where is termed slowness vector. It points in the same direction as and has the magnitude , which is the inverse of the propagation velocity. From (14.4), it can be readily seen that the direction of propagation is given by . Let the origin of the coordinate system be close to the sensor array. The slowness vector can then be expressed as

(14.5)

where and denote the elevation and azimuth angles, respectively. Both parameters characterize the direction of propagation and are referred to as direction of arrival (DOA) (see Figure 14.1).

Far-field assumption: For far-field sources, the propagation distance to a sensor array is much larger than the aperture of the array, the DOA parameter is approximately the same to all sensors. According to (14.2), the wave front of constant phase at time instant t is a plane perpendicular to the propagating direction given by . The term, plane wave assumption is alternatively used in the literature.

3.14.2.2 Frequency domain description

In an ideal medium, the propagation between signal sources and a sensor array is considered as a linear time-invariant system. Due to the applicability of the superposition principle and the Fourier transform, the analysis of wave propagation is greatly simplified. In the following, we will develop a general frequency domain model and discuss the narrow band case. The general model is useful for broadband data that may be measured in underwater acoustical or geophysical experiments. The narrow band model is preferred in applications where the signal bandwidth is much smaller than the carrier frequency, for example, wireless communications and radar.

3.14.2.3 Uniqueness

A fundamental issue in the direction finding problem is whether the DOA parameters can be identified unambiguously. From the ideal data model (14.12) or (14.17), we know that the array output lies in a subspace spanned by the columns of the array steering matrix if the noise part is ignored. For simplicity, we will present the results for the model (14.17). Assume any subset of vectors , are linearly independent. The study in [9,10] specifies the conditions for the maximal number of sources that can be uniquely localized in terms of the number of sensors M and the rank of the signal correlation matrix R. The condition (1) guarantees uniqueness for every batch of data, while the weaker condition (2) guarantees uniqueness for almost every batch of data, with the exception of a set of batches of measure zero. When all sources are uncorrelated implying that , condition (1) is always satisfied and uniqueness is always guaranteed. When the sources are fully correlated, , then uniqueness is ensured if by condition (1). The weaker condition (2) leads to a less stringent condition . Details on the proof are to be found in [10].

3.14.3.1 Conventional beamformer

The conventional beamformer, also termed as delay-and-sum beamformer, combines the output of each sensor (14.6) coherently to obtain an enhanced signal from the noisy observation. For simplicity, assume for now. In its most general form, the conventional beamformer compensates the time delayed observation at the mth sensor by the amount of . The sum of aligned sensor outputs leads to an estimate for the signal:

(14.21)

From the above equation, it is clear that the signal to noise ratio is improved by a factor of M. For wideband data, the sum in (14.21) is often called true time-delay beamforming. It can be approximately implemented using various filtering techniques, see e.g., [6,7]. For narrow band data, the shift in the time domain becomes phase shift in the frequency domain. Therefore, we have

(14.22)

where is the steering vector evaluated at the look direction . Since for any steering vectors, , the weight vector has unit length and

(14.23)

An estimate for the power spectrum is then obtained as

(14.24)

In the context of spectral analysis, the above expression corresponds to the periodogram in the spatial domain [3]. The expected value of is the convolution between the beam pattern and the true power spectrum. A good beam pattern should be as close to the delta function as possible to minimize leakage from neighboring frequencies.

For a uniform linear array, the beam pattern has a main lobe around the look direction . The Rayleigh beamwidth, the distance between the first two nulls of , is approximately given by

(14.25)

The beamformer can only distinguish two sources with DOA separation larger than half of . Note that is the ratio between actual distance D and wavelength . As is inversely proportional to Md, the aperture of the array, the resolution capability improves with increasing number of sensors and sensor spacing. However, is the maximally allowed sensor distance. For , grating lobes appear in the beampattern and create ambiguity in the DOA estimation.

For a standard ULA with sensors, , the beamwidth , meaning that the DOA separation between two sources must be larger than 11° to generate two peaks in the power spectrum .

3.14.3.2 Minimum variance distortionless response (MVDR) beamformer

The minimum variance distortionless response (MVDR) beamformer [1] alleviates the resolution limit of the conventional beamformer by considering the following constrained optimization problem:

(14.26)

(14.27)

The objective function (14.26) represents the output power to be minimized. The constraint (14.27) ensures that signals from the desired direction remain undistorted. In other words, while the power from all other directions is minimized, the beamformer concentrates only on the look direction. The behavior of the MVDR beamformer was also discussed by Lacoss [11]. The resulting beampattern has a sharp peak at the target DOA, leading to resolution capability beyond the Rayleigh beamwidth. Applying the method of Lagrange multipliers, we obtain the solution as

(14.28)

Replacing (14.28) into (14.20), one obtains the power function as

(14.29)

A condition on the MVDR beamformer follows immediately from (14.28) where the inversion of the sample covariance matrix requires that is full rank, implying that the number of samples must be larger than the number of sensors, i.e., . When rank deficiency occurs or the sample number is small compared to the number of sensors, a popular technique known as diagonal loading is often employed to improve robustness. As the name implies, the sample covariance matrix (14.14) is modified by adding a small perturbation term to improve the conditioning:

(14.30)

where is a properly chosen small number and is an identity matrix. The choice of the coefficient is essential. Several criteria for optimal choice of diagonal loading have been reported in [12] and the references therein.

A variant of the MVDR beamformer, proposed in [13], replaces the constraint (14.27) by . This formulation leads to the adapted angular response spectrum . This Borgiorri-Kaplan beamformer is known to provide higher spatial resolution than that of the MVDR beamformer. In [14], the denominator of (14.29) is replaced by where . Simulation results therein show that using higher order covariance matrix has superior resolution capability and robustness against signal correlation and low SNR.

The performance of the MVDR beamformer depends on the number of snapshots, array aperture, and SNR. Several interesting results are reported in [15]. In the presence of coherent or strongly correlated interferences, the performance of the MVDR beamformer degrades dramatically. Alternative methods addressing this issue are reported in [16–21]. Due to the distortionless response constraint, the MVDR beamformer is sensitive to errors in the target direction and array response imperfection. Robust methods to tackle this problem have been suggested in [22,23].

3.14.3.3 Sparse data representation based approach

The beamforming methods localize the signal sources by estimating the power spectrum associated with various DOAs. Since the number of signals is usually small in array processing, the methods proposed in [24,25] view DOA estimation as sparse data reconstruction and assign DOA estimates to signals with nonzero amplitude. In this approach, the first step is to find a sparse representation of the array output data. The beamforming output in the frequency domain [24] or the array observation (14.12) [25] can be used to construct a sparse data representation. Then the underlying optimization problem (typically convex) will be solved to find nonzero components. DOA estimates are obtained from angles associated with nonzero components. Recently this approach has attracted many researchers’ attention thanks to advances in the theory and methodology of sparse data reconstruction [26].

For representational convenience, we follow the formulation in [25]. Let be a sampling grid of source locations of interest. An important assumption here is that the number of signals is much smaller than the number of sample grids, i.e., . The overcomplete array manifold matrix consists of steering vectors. The signal vector has a nonzero component if a signal source is present at . For a single snapshot, the array output (14.12) can be re-expressed in terms of the sparse vector as:

(14.31)

Now the problem reduces to finding the nonzero component in . In the noiseless case, the ideal measure would be which counts the nonzero entries. This would in fact lead to the deterministic ML method over a grid search. But this metric will lead to a complicated combinatorial optimization problem. Therefore, one tries to approximate the solution by using norm, . The significant advantage of relaxation is that the convex optimization problem,

(14.32)

has a unique global minimum and can be solved by computationally efficient numerical methods such as linear programming. For noisy measurements (14.31), the constraint can not hold and needs to be relaxed. An appropriate objective function is suggested in [24,25]

(14.33)

where is a regularization parameter.

For multiple snapshots, we define the data matrix , the signal matrix and the noise matrix . They are related as follows:

(14.34)

To measure sparsity for multiple time samples, we define the ith row vector of corresponding to a particular DOA grid point as and compute its norm . Then the spatial sparsity is imposed on the vector . The multiple sample version of (14.33) becomes

(14.35)

where is the Forbenius norm. The regularization parameter is a tradeoff between the fit to data and the sparsity. In [24,25], statistically motivated strategies for selecting are discussed.

The computational cost for solving (14.35) increases significantly with the number of snapshots N. A coherent combination based on singular value decomposition (SVD) of the data matrix is suggested in [25]. A mixed norm approach for joint recovery is proposed in [27]. This problem can be avoided when other forms of sparsity are used, for example, the beamforming output in [24] and the covariance matrix in [28]. The resolution capability of this approach is investigated in [29].

Simulation results in the above mentioned references show that the sparse data representation based approach has a much better resolution than the conventional and MVDR beamformers at the expense of increased computational cost. Another advantage over the subspace methods is the improved robustness against signal coherence. However, for low SNRs and closely located sources, the relatively high bias remains an challenging issue for this approach.

3.14.3.4 Numerical examples

In this section, the beamforming based methods discussed previously are tested by numerical experiments. In the simulation, a uniform linear array of 12 sensors with inter-element spacings of half a wavelength is employed. The narrow band signals are generated by uncorrelated signals of various strengths. The signal to noise ratio of the first and second signals are given by [5 0] dB, respectively. The number of snapshots is in each Monte Carlo trial.

Figure 14.2 shows the normalized spectra obtained from conventional beamformer, MVDR beamformer and sparse data representation over to for well separated sources located relative to the broadside. All the three methods exhibit two peaks at the reference locations. For the second experiment, the reference DOA parameter is given by , which corresponds to closely located signals. As shown in Figure 14.3, the conventional beamformer only leads to one maximum between the true DOAs and does not recognize the existence of two signals. On the other hand, the MVDR beamformer and the sparse data representation based approach perform well in resolving two signals.

In the third experiment, we compare the estimation accuracy of these methods. To avoid resolution problem, the reference DOA parameter is chosen as . Both signals have equal power with SNR running from −5 dB to 20 dB in a 1 dB step. Figure 14.4 depicts the root mean squared error (RMSE) obtained from 1000 trials. For all three methods, RMSE decreases with increasing SNR. The sparse data representation based method has an overall best performance over the entire SNR range. The MVDR beamformer lies between the other two methods. The gap between these methods becomes most significant at low SNRs. For example, at SNR = −5 dB, the RMSE of conventional beamformer is which is more than three times that of the sparse data representation based method with RMSE = 1.5°.

From the simulation results, we have observed the resolution limitation of the conventional beamformer. Improved resolution capability and estimation accuracy can be achieved by the MVDR beamformer and computationally involved sparse data representation based estimator.

3.14.4.1 MUSIC

The MUSIC algorithm suggested by Schmidt [2,32], and Bienvenu and Kopp [31] exploits the orthogonality between signal and noise subspaces. From (14.37), we know that any vector satisfies

(14.38)

Assume the array is unambiguous; that is, any collection of P distinct DOAs forms a linearly independent set . Then the above relation is valid for P distinct columns of . Motivated by this observation, the MUSIC spectrum is defined in terms of the estimated noise eigenvectors as

(14.39)

For high SNR (or large N) and uncorrelated signal sources, the MUSIC spectrum exhibits high peaks near the true DOAs. To find the DOA estimates, we calculate over a fine grid of and locate the P largest maxima of . In comparison with the MVDR beamformer (14.29), the MUSIC spectrum uses the projection matrix rather than . To get more insight, assume a perfect spatial correlation matrix. Then, for noise eigenvalues and approaches . Then MUSIC may be interpreted as a MVDR-like method with a correlation matrix calculated at infinite SNR. This explains the superior resolution of MUSIC than MVDR [3].

In [33,34], an alternative implementation of MUSIC is suggested to improve estimation accuracy. The idea behind the sequential MUSIC is to find the strongest signal in each iteration and then remove the estimated signal from the observation for the next iteration. As theoretical analysis and numerical results in [34] show the advantage of sequential MUSIC over standard MUSIC is significant for correlated signals. The Toeplitz approximation method [35] provides another implementation of MUSIC specific to uncorrelated sources with a ULA.

For a uniform linear array, MUSIC has a simple implementation. Let where , the steering vector (14.16) has the form:

(14.40)

The inverse of the MUSIC spectrum (14.39) becomes

(14.41)

The root-MUSIC algorithm [36] finds the roots of the complex polynomial function rather than searching for maxima of the MUSIC spectrum. Among the possible candidates, P roots that are closest to the unit circle on the complex plane are selected to obtain DOA estimates. Since , the DOA parameters are given by . It is known that root-MUSIC has the same asymptotic performance as standard MUSIC. In the finite sample case, root-MUSIC has a much better threshold behavior and improved resolution capability [37]. This is explained by the fact that the radial component of the errors in will not affect . Since the search procedure in standard MUSIC is replaced by solving the roots of a polynomial in root-MUSIC, the computational cost is significantly reduced. However, while standard MUSIC is applicable to arbitrary array geometry, root-MUSIC requires a ULA. When ULAs are not available, one can apply array interpolation techniques [38] to approximate the array response. For more details on array interpolation, the reader is referred to Chapter 16 of this book.

The extension of standard MUSIC to the two dimensional case is straightforward. The 2D steering vector (14.8) is used in the MUSIC spectrum, searching for the P largest maxima over a two dimensional space. For root-MUSIC, an additional ULA is required to be able to resolve both azimuth and elevation [39]. More algorithms and results regarding two dimensional DOA estimation are to be found in Chapter 15 of this book.

While the MUSIC algorithm utilizes all noise eigenvectors, the Minimum Norm (Min-Norm) algorithm suggested in [40,41] uses a single vector in the noise space. A comprehensive study on the resolution capability of MUSIC and the Min-Norm algorithm can be found in [42].

3.14.4.2 ESPRIT

The ESPRIT (Estimation of Signal Parameters via Rotational Invariance Techniques) algorithm proposed by Roy and Kailath [43] exploits the rotational invariance property of two identical subarrays and solves the eigenvalues of a matrix relating two signal subspaces. A simple way to construct identical subarrays is to select the first elements and the second to the Mth elements of a ULA (see Figure 14.5). The array response matrices of the first and second subarrays are then expressed as

(14.42)

where and are selection matrices of the first and second subarrays. They consist of an identity matrix and an zero vector

(14.43)

Define . From (14.42), we know that the two subarrays have the same array response up to a phase shift due to the distance between them. This observation leads to the shift invariance property

(14.44)

where . Note that ESPRIT is applicable for array geometries other than ULAs as long as the shift invariance property holds, see e.g., [43–45].

Recall that the signal subspace of the original array and the signal eigenvectors span the same subspace; therefore, they are related through a nonsingular linear transformation :

(14.45)

Multiplying both sides of (14.45) with and ,

(14.46)

Combining (14.44) and (14.46) yields the relation between and :

(14.47)

Since the matrix is similar to the diagonal matrix , both matrices have the same eigenvalues, .

Using estimates in (14.47), one can apply LS (Least Squares) or TLS (Total Least Squares) to obtain [46]. Finally, DOA estimates are obtained from eigenvalues of by the formula . The computational burden of the ESPRIT algorithm can be reduced by using real-valued operations as proposed in [44].

3.14.4.3 Signal coherence

In the development of subspace methods, we have made an important assumption that the rank of the signal covariance matrix equals the number of signals P so that the signal eigenvectors spans the same subspace as the column space of the array manifold matrix. However, this condition no longer holds when two signals are coherent, meaning that the magnitude of the correlation coefficient of the signals is one. Coherent signals are often encountered in wireless communications as a result of a multipath propagation effect or smart jamming in radar systems. In the presence of signal coherence, becomes rank deficient, leading to divergence of signal eigenvectors into the noise subspace. Since the property (14.38) is not satisfied, performance of subspace methods degrades significantly. To mitigate the effect of signal coherence, one could apply forward-backward averaging or spatial smoothing techniques. The former requires a ULA and can handle two coherent signals. The latter requires arrays with a translational invariance property and is able to deal with maximally P coherent signals.

Let denote the exchange matrix comprised of ones on the anti-diagonal and zeros elsewhere. For a ULA, the steering vector (14.16) has an interesting property:

(14.48)

which implies

(14.49)

where . The backward covariance is defined as

(14.50)

The forward-backward covariance matrix is obtained by averaging of and the standard array covariance matrix :

(14.51)

Applying the property (14.49), the modified signal covariance matrix is then given by

(14.52)

The coherent signals are de-correlated through phase modulation by the diagonal elements of . The forward-backward ESPRIT is equivalent to the unitary ESPRIT [44], because it only uses real valued components.

In a general case where more than two coherent signals are present, we need a more powerful solution to restore the rank of the signal covariance matrix. The spatial smoothing technique, first proposed in [47] and extended in [38,48,49], exploits the degrees of freedom of a regular array by splitting it into several identical subarrays. Let denote the number of sensors of a subarray. For a ULA of M elements, the maximal number of subarrays is . The array response matrix of the lth subarray is related to as

(14.53)

where the selection matrix is . The spatially averaged covariance matrix is then given by

(14.54)

In the case of a ULA, one can combine the forward-backward averaging (14.51) with the spatial smoothing. In [48,50], it was shown that under mild conditions, the signal covariance matrix obtained from forward-backward averaging and spatial smoothing is nonsingular. Since the subarrays have a smaller aperture than the original array, the signal coherency is removed at the expense of resolution capability. The two dimensional extension of spatial smoothing is addressed in [51–53].

3.14.4.4 Numerical examples

We demonstrate the performance of the subspace methods presented previously by numerical results. A uniform linear array of 12 sensors with inter-element spacings of half a wavelength is employed. In this case, the application of root-MUSIC is straightforward. Narrow band signals are generated by well separated sources of equal strengths located at . The number of snapshots is . Both signals are equal power with SNR running from −5 dB to 20 dB. The two subarrays used in ESPRIT are ULAs comprised of 11 elements.

In the first experiment, we consider uncorrelated signals. For comparison, the MVDR beamformer is applied to the same batch of data. The empirical RMSE is obtained from 1000 trials. From Figure 14.6, one can observe that root-MUSIC, denoted by R-MUSIC, outperforms standard MUSIC and ESPRIT. All the subspace methods have lower estimation errors than the MVDR beamformer. The performance difference is most significant at low SNRs. For SNR close to 20 dB, all methods behave similarly. The superior performance of root-MUSIC compared to standard MUSIC is expected as predicted by the theoretical analysis [37]. The estimation error of ESPRIT is higher than both MUSIC algorithms due to the reduced aperture.

In the second experiment, two correlated signals are considered with real valued correlation coefficient . One can observe from Figure 14.7 that the performance of all methods degrade rapidly. At , the RMSE is more than twice the RMSE in the uncorrelated case. Both MUSIC-based algorithms have almost identical performance. They are slightly better than ESPRIT. The curve of ESPRIT almost coincides with that of MVDR. These observations indicate that subspace methods are very sensitive to signal correlation and can not provide accurate estimates when rank deficiency occurs. If we use the forward-backward averaged sample covariance matrix (14.51) in the subspace methods, denoted by FB-ESPRIT, FB-MUSIC, and FB-R-MUSIC, respectively, the estimation accuracy improves significantly as the three curves at the bottom show. In comparison with Figure 14.6, the RMSE increases only slightly when the FB technique is applied. For a detailed discussion on highly correlated signals, the reader is referred to Chapter 15 of this book.

3.14.5.1 The maximum likelihood approach

The maximum likelihood method is a systematic tool for constructing estimators. Based on the statistical model for data samples, it maximizes the likelihood function over the parameters of interest to derive estimates. The well known properties of ML estimation include asymptotic normality and efficiency under proper conditions [54]. For DOA estimation, the application is straightforward. Recall the data model in (14.17)

(14.55)

We assume the noise is temporally independent and complex normally distributed with zero mean and covariance matrix , i.e., . In the array processing literature, two different interpretations of the source signals lead to the deterministic and the stochastic ML estimators.

3.14.5.2 Implementation

In the derivation of ML estimators, we have reduced the size of the problem by concentrating the signal and noise parameters. The resulting objective functions: (14.60) and (14.66) depend only on the nonlinear parameters. Maximization of both criteria still requires multi-dimensional searches. Hence, efficient implementation of the ML estimators becomes an important issue. The alternating projection algorithm [64] is an iterative technique for finding the maximum of the concentrated likelihood function (14.60). It performs maximization with respect to a single parameter, while all other parameters are held fixed. In [65], Newton-type methods are suggested for the large sample case.

In the following, we will present the statistically motivated expectation and maximization (EM) and space alternating generalized EM (SAGE) algorithm. The multidimensional search in the original problem can be replaced by several one dimensional maximizations. Both algorithms assume the deterministic signal model so that the suggested augmentation scheme is valid. It is possible to derive EM and SAGE for stochastic ML for uncorrelated signals, see e.g., [66]. When a ULA is available, the iterative quadratic maximum likelihood (IQML) algorithm can be applied to minimize the deterministic likelihood function. A common feature of these methods is that a good initial estimate is required for the convergence to the global maximum. One way to obtain the initial estimate is via other simpler methods such beamforming techniques or subspace methods. Another approach is to optimize the ML criteria directly by stochastic optimization procedures such as the genetic algorithm (GA) [67], simulated annealing [68] and particle swarm method [69] prior to the local maximization algorithms.

3.14.5.3 Subspace fitting methods

The maximum likelihood approach exploits the parametric model and statistical distribution of array observations fully and exhibits excellent performance. The subspace fitting method [88–90] provides a unified framework for the deterministic ML estimator and subspace based methods. More specifically, it uses a nonlinear least square formulation

(14.87)

where is a data matrix and is any matrix of conformable dimension. For fixed , the minimization with respect with measures how well the column spaces of and match. Replacing the closed form solution back into (14.87) results in a concentrated criterion:

(14.88)

Clearly, the deterministic ML estimator (14.61) can be obtained by using array observations as the data matrix .

The subspace fitting criterion is derived when the estimated signal eigenvectors are inserted as data . The weighted least square fitting solution to (14.87) has the expression:

(14.89)

where the weighting matrix is Hermitian and positive definite. The analysis in [89,90] shows that the estimator is strongly consistent and asymptotically normally distributed. Minimization of the error covariance matrix of leads to the optimal weighting matrix where . Recall that the diagonal matrix contains P signal eigenvalues and denotes the noise eigenvalue. In practice, both and are estimated from data. The weighted subspace fitting (WSF) algorithm (or the method of direction estimation (MODE) [91]) is obtained when a consistent estimator is inserted into (14.89):

(14.90)

The signal subspace fitting formulation (14.89) has certain advantages over the data-domain nonlinear least square (14.87), in particular when . It is then significantly cheaper to compute (14.89) than (14.87).

In addition to the criterion (14.89), a noise subspace fitting formulation is developed in [91]. Although the resulting criterion is quadratic in the steering matrix , the noise subspace fitting criterion can not produce reliable estimates in the presence of signal coherence. The covariance matching estimator [92] that will be presented shortly can be formulated as (14.87).

The implementation of nonlinear least square type criteria (14.87) has been addressed in several papers [64,77,93]. A common feature of these methods is similar to the SAGE algorithm in the sense that instead of maximizing all parameters simultaneously, a subset of parameters, or the parameters associated with one signal source is computed in one step while keeping other parameters fixed. The RELAX procedure [93] is similar to the SAGE algorithm (14.77) and (14.79), although it has a simpler motivation and interpretation. The WSF (or MODE) criterion (14.90) can be formulated in terms of polynomial coefficients for ULAs by the expression (14.84) [91]. An iterative implementation, iterative MODE, similar to IQML is suggested in [84]. Theoretical and numerical results in [84] show that iterative MODE provides more accurate estimates and is computationally more efficient than IQML.

3.14.5.4 Covariance matching estimation methods

The covariance matching estimation methods are referred to as generalized least squares in the statistical literature. The application to array processing has led to several interesting algorithms [92,94–97]. Covariance matching can treat temporally correlated data and provides the same large sample properties as maximum likelihood estimation at often a lower computational cost [92].

Recall that the array output covariance matrix is give by . By stacking the columns of , one obtains the following expression:

(14.91)

where the elements of are source signal covariance parameters, is a known matrix, and is a given function of the unknown parameter vector . In general, the DOA parameter vector enters in a nonlinear fashion. An estimate for can be obtained from the sample covariance matrix by . Fitting the data to the model (14.91) in the weighted least squares sense leads to the following criterion

(14.92)

where the weighting matrix is a consistent estimate of the covariance matrix . The symbol denotes the Kronecker matrix product.

The least square criterion is separable in the linear and nonlinear parameters. Minimizing (14.92) over the linear parameter vector results in a closed form expression:

(14.93)

Substituting (14.93) into (14.92) leads to a concentrated criterion:

(14.94)

where denotes a projection matrix onto the column space of . To apply (14.94), one needs to find the matrix corresponding to the covariance matrix of the array observations. Based on the extended invariance principle, it was shown that the covariance matching estimator is a large sample realization of the ML method and asymptotically efficient [92]. A drawback of the covariance matrix matching based estimation methods is that they inherently assume a large sample size, and are less suitable to scenarios involving a small number of observations and high SNRs.

3.14.5.5 Performance bound

The performance of an estimator is measured by its average distance to the true parameters. In many cases, one is interested in the following questions: (1) Whether it converges to the true parameter as the number of data samples approaches infinity. (2) Whether the asymptotic error covariance matrix attains the Cramér-Rao bound (CRB). These two properties, consistency and efficiency, and the error covariance matrix are major concerns in a performance study. In this section, we will outline several important results. A comprehensive coverage on performance analysis is given in Chapter 14 in this book.

It is well known that the estimation error covariance of any unbiased estimator is lower bounded by the Cramér-Rao bound [54]. The Crámer-Rao bounds for the conditional and unconditional model are derived in [98–100], respectively. The conditional CRB, denoted by is given by

(14.95)

where contains the first derivative of steering vectors, , and . For , the conditional CRB tends to the limit

(14.96)

The unconditional CRB, denoted by , is given by

(14.97)

From (14.95) and (14.97), we can observe that the CRBs decrease with increasing number of snapshots. Theoretical analysis and simulation results also show that the CRBs decrease as the number of sensors or SNRs grow.

3.14.5.6 Numerical examples

In this section, we compare the performance of conditional ML estimator and root-MUSIC algorithm in a simulated environment. A ULA of 12 elements with half wavelength spacing is employed to receive two far-field narrow band signal sources of equal strengths located at . The sample covariance matrix is estimated from snapshots. Each experiment performs 500 Monte Carlo trials.

The RMSEs for DOA estimates and the conditional CRB (14.95) for uncorrelated and correlated signals are depicted in Figures 14.8 and 14.9, respectively. For the uncorrelated case, ML performs slightly better than root-MUSIC; in particular, at low SNR between −5 and 5 dB. In the correlated case with the correlation coefficient , while the deterministic ML estimator performs as well as in the uncorrelated case and close to the CRB, root-MUSIC no longer provides reliable estimates. As can be observed from Figure 14.9, even for SNR as high as 10 dB, root-MUSIC has RMSE larger than . The difference between ML and root-MUSIC is most significant at low SNRs. In other words, the ML estimator is more robust than root-MUSIC against signal correlation and low SNRs. Although the performance of root-MUSIC is improved by forward-backward averaging, the RMSE is still larger than the ML approach. For SNR below 0 dB, it is twice as much as that of ML.

As mentioned previously, the ML estimator requires multi-dimensional nonlinear optimization. We compare three different implementations: (1) matlab function fmincon, (2) EM algorithm, (3) SAGE algorithm. The initial estimates for (1). are found by the genetic algorithm. The initial estimates for EM and SAGE are fixed at to simplify the investigation of their convergence behavior. Figure 14.10 shows that all three methods find ML estimates and achieve the same accuracy. To compare the convergence behavior of EM and SAGE, we plot the average log-likelihood value vs. iterations in Figure 14.11. As the convergence analysis in [74] predicted, SAGE converges faster than EM. It requires only 6 iterations to reach the final likelihood value, while EM requires 15 iterations. This is further confirmed by the average total number of iterations shown in Figure 14.12. As we can observe, at SNR from −10 dB to 5 dB, EM needs more than twice iterations than SAGE. For moderate to high SNR, the number of iterations of EM always exceeds that of SAGE by at least six iterations. This suggests that EM requires more computational time than SAGE. It should be mentioned that the genetic algorithm [67] requires more than 10 times as long computational time compared to SAGE.

3.14.6.1 Wideband maximum likelihood estimation

In Section 3.14.2.2.1, the data model (14.10) was developed for a continuous temporal array output . In practice, the array outputs are temporally sampled at a properly chosen frequency. The data within an observation interval is divided into K non-overlapping snapshots of length and Fourier-transformed. For large number of samples, the frequency domain data can be modeled by (14.10). Under some regularity conditions including stationarity of array outputs, the following asymptotic properties hold [107]:

In the following, we assume that . Because of the independency between different frequency bins, the likelihood function is a product of those associated with various frequencies. For the deterministic data model, the log-likelihood function is given by

(14.98)

where the signal vector and noise vector contain signal and noise parameters of J frequencies. Similar to the narrow band case, the likelihood function can be concentrated with respect to the signal and noise parameters, leading to the concentrated likelihood function

(14.99)

where the sample covariance matrix and is the orthogonal complement of the projection matrix . Note that the summand in (14.99) has the same form as the narrow band likelihood function (14.61). The broadband criterion can be considered as an arithmetic average of narrow band likelihood functions over frequencies. The deterministic ML estimate is computed by maximizing this criterion or minimizing the negative log-likelihood:

(14.100)

For the stochastic signal model, the log-likelihood function is given by

(14.101)

where contains signal spectral parameters of all frequencies and includes noise power parameters. Similar to the narrow band case, the stochastic likelihood function can be simplified by substituting ML estimates of signal and noise parameters into (14.101), leading to the concentrated criterion:

(14.102)

where is an estimate for the noise parameter. Similar to the deterministic case, (14.102) is an average of the narrow band likelihood criterion (14.61) over frequencies. The stochastic ML estimator is then obtained by maximizing this criterion or minimizing the negative likelihood:

(14.103)

The performance analysis in [66] shows that under regularity conditions, is an asymptotically consistent, efficient estimator for . The deterministic ML estimator is asymptotically consistent, but not efficient. The computation complexity can be also simplified by the EM or EM-like algorithms [74,76].

3.14.6.2 Coherent signal subspace methods

The coherent signal subspace methods proposed in [105] combine the broadband data by multiplying each frequency with the focusing matrix satisfying the following property

(14.104)

where is a selected reference frequency. The coherently averaged covariance matrix is given by

(14.105)

where is the sum of noise level over frequencies and . Given the known noise structure , the eigenvalue/eigenvector pairs of satisfy the same properties (14.36), (14.37) as in the narrow band case. Hence, the subspace methods introduced previously can be applied to the new matrix (14.105).

The design of (14.104) requires a rough estimate of the DOA parameter, which can be obtained from the narrow band MVDR or conventional beamformer. In [104], the rotational signal subspace focusing matrix is developed by solving the constrained optimization problem:

(14.106)

(14.107)

The solution to (14.106) is given by , where the columns of and are left and right singular vectors of . The selection of reference frequency and accuracy improvement are discussed in detail in [104,105]. Within the class of signal subspace transformation matrices, the rotational subspace transformation matrix is well known for their optimality in preserving SNR after focusing [108]. In practice, the spatial correlation matrix is replaced by the sample covariance matrix . By (14.105), we compute the coherently averaged sample covariance matrix and construct coherent signal/noise subspaces from . Then standard subspace methods are applied with as the reference frequency for DOA estimation.

In [109], coherent subspace averaging is achieved by using weighted signal subspaces instead of the array correlation matrix in (14.105), where contains signal eigenvectors at frequency and is a weighting matrix. While the aforementioned methods concentrates on the design of the best coherently averaged signal subspaces and finding the DOA estimates by standard narrow band eigenstructure based algorithms such as MUSIC, the test of orthogonality of projected subspaces (TOPS) algorithm proposed in [110] utilizes the property of transformed signal subspaces and test whether the hypothesized subspaces and the noise subspaces are orthogonal. A significant advantage of this approach is that it does not require initial DOA estimates. Simulation results in [110] show that TOPS performs better than the aforementioned methods in mid SNR ranges, while the coherent methods work best at low SNR and incoherent methods work best at high SNR.

3.14.7.1 Nonparametric methods

We have learned in subspace methods that the array correlation matrix (14.13) has the eigen-decomposition where the diagonal matrix consists of the P largest eigenvalues and contains corresponding eigenvectors. The remaining eigenvalues/vectors are included in and in a similar way. When the signal covariance matrix is full rank, the eigenvalues satisfy the property

(14.108)

The smallest noise eigenvalues are equal to . This observation suggests that the number of signals can be determined from the multiplicity of the smallest eigenvalue. In practice, the correlation matrix is unknown and the eigenvalues are estimated from the sample covariance matrix . The ordered sample eigenvalues are distinct with probability one [8].

The sphericity test, originating from the statistical literature [119], is modified for detection purpose in [115]. Therein, a series of nested hypothesis tests is formulated to test the equality of eigenvalues, i.e.,

(14.109)

where and denote the null hypothesis and alternative, respectively. Starting from , the test proceeds to the next hypothesis if is rejected. Upon acceptance of , the test stops, implying all remaining tests are true and leading to the estimate . For non-Gaussian distribution and small samples case, the test statistic does not have a closed form expression for null distribution. To overcome this problem, a procedure using bootstrap techniques are developed in [114]. The test for unknown noise fields is suggested in [120]. Recently, due to the development of random matrix theory, the eigenvalue based multiple test is re-visited for the small sample case in [121,122] and the references therein.

The information theoretic criteria based approach views signal detection as model order selection. The Akaike’s information criterion (AIC) and Rissanen’s minimum description length (MDL) was derived for signal detection in [111]. In the derivation, the data set is parameterized by the eigenvalues and eigenvectors of correlation matrix , rather than the DOA parameter. Maximization of the log-likelihood function leads to the AIC criterion

(14.110)

and the MDL criterion

(14.111)

The number of signals is determined as the minimizing value of AIC or MDL, where denotes the maximal number of signals. Eqs. (14.110) and (14.111) show that both criteria has the first term in common, which is a ratio between geometric mean and arithmetic mean of the smallest eigenvalues. The penalty term of AIC depends only on the number of free adjustable parameters, while the penalty term of MDL depends also on the data length N. In general, AIC tends to overestimate the number of signals while MDL is consistent as the number of samples approaches infinity [111,123]. Various improvement strategies for MDL for situations involving fully correlated signals, correlated noise and small samples have been suggested in [112,124–127] and references therein.

3.14.7.2 Parametric methods

In parametric methods, the DOA parameter in the model (14.12) enters the algorithms directly. Determination of the number of signals can be formulated as a multiple hypothesis test. In the multiple hypothesis test approach, we consider a series of nested hypotheses.

(14.112)

The subscripts and i are used to emphasize the dimension of the steering matrix and the signal vector under the null hypothesis and the alternative , respectively. Here, the signal vectors are considered as unknown and deterministic.

In [116,118,128], a sequential test procedure is developed to detect the signal one after another. Starting from noise only case, is tested against . If is rejected, a new signal is declared as detected and the test procedure proceeds to the next hypothesis . It stops when the null hypothesis is accepted, implying that no further signal can be detected. The number of signals is then estimated by the dimension of the signal vector under the accepted null hypothesis. The test statistics are constructed by the generalized likelihood ratio principle. In the narrow band case, it leads to an F-test similar to that suggested in [129]. For broadband data, a closed form expression for the null distribution is not available. In this case, bootstrap techniques or Edgeworth expansions can be applied to approximate the significance level or test threshold. The global significance level in the sequential test procedure is usually controlled by Bonferroni-type procedures. As each test is conducted at a much lower level, results may be conservative when the size of the problem increases. A more powerful test procedure based on the false discovery rate criterion is developed in [117]. A joint estimation and detection procedure was also investigated in [65].

Simulation shows that the multiple hypothesis approach has superior performance than information theoretic approach [117]. In particular, signal coherence has little impact on the performance. Due to ML estimates required in the test, parametric methods are computationally more expensive than eigenvalue based methods.

3.14.7.3 Additional issues

When the estimated number of signals, , provided by detection algorithms is accurate, the performance of DOA estimation is well studied in the literature. In the low SNR region and small sample case, the number of signals may be over- or underestimated. In the presence of overestimated signals, the true DOA parameters are included in the oversized parameter vector with increased variance for the true parameters. In the case of under estimation, the inaccuracy in signal numbers will lead to bias and increased mean squared errors [130]. Robust algorithms have been suggested in [131,132] to retrieve information when the number of signals is unknown.

3.14.8.1 Tracking

Localization of moving sources is essential to many applications. In the classical tracking problem, the DOA estimates obtained from array data are considered as input data for track estimation. The main task is to match DOA estimates and to contacts, and many solutions have been developed to solve the data association problem [133,134]. An alternative approach incorporates target motion into the likelihood function and estimates the DOA parameter, and velocity directly from data [135–137]. In [138,139], the EM algorithm is suggested to reduce the computational cost for maximizing the likelihood function. To further simplify the implementation, the recursive EM algorithm is developed in [128,140]. The recursive EM algorithm is a stochastic approximation procedure for finding ML estimates [141]. With a specialized gain matrix derived from the EM algorithm, it has a simple implementation and leads to asymptotic normality and consistency. With a proper formulation, it can also be used for estimating time varying DOA parameters.

For subspace methods, how to compute the time-varying signal or noise subspaces efficiently becomes the most important step. In early works, classical batch Eigenvalue Decomposition/SVD techniques have been modified for the use in adaptive processing. Fast computation methods based on subspace averaging were proposed in [142–144]. Another class of algorithms considers ED/SVD as a constrained or unconstrained optimization problem [145–149]. For example, in [149], it is shown that the signal subspace can be computed by solving the following unconstrained optimization problem:

(14.113)

where denotes the matrix argument and r is the number of signal eigenvectors. The aim of subspace tracking is to compute efficiently at the time instant n from the subspace estimate at time instant . For time-varying subspaces, the expectation in (14.113) is replaced by an exponentially weighted sum of snapshots to ensure the samples in the distant past is down weighted. In addition to low computational complexity, fast convergence and numerical stability are also desired properties in the implementation of subspace tracking techniques. Once the subspace estimates are updated, the DOA estimates are computed by subspace methods presented previously.

3.14.8.2 Signals with known structures

In some applications, the source signals exhibit specific structures and can be exploited for DOA estimation. For example, in communication systems, modulated signals are characterized by cyclostationarity, which is referred to as being periodically correlated. This property allows estimation of DOAs of only those signals having specified cycle frequency. Also, the noise can have unknown spatial characteristics as long as it is cyclically independent from signals of interest. Several direction finding algorithms were suggested and analyzed in [150–154].

In standard array processing methods, array data are assumed to be Gaussian and completely characterized by second order statistics. In the presence of non-Gaussian signals, higher order statistics can be exploited to the advantage of Gaussian noise suppression and increased aperture [155–158]. A common feature of both types of methods is the requirement of large amount of data samples to achieve comparable results as standard algorithms.

3.14.8.3 Spatially correlated noise fields

Most existing array processing methods assume that the background noise is spatially white, i.e., the covariance matrix is proportional to the identity matrix. This assumption is often violated in practical situations [159]. If the noise covariance matrix is known or estimated from signal-free measurements, the data can be pre-whitened. In the absence of this knowledge, the quality of DOA estimates degrade dramatically at low SNR [160,161].

Methods that take small errors in the assumed noise covariance into account are proposed in [63,162,163]. These algorithms are not applicable when the noise covariance is completely unknown, unless SNR is very high. Another approach considers parametric noise models and estimates DOA and noise parameters simultaneously [56,164,165]. In this approach, the additional noise parameters require extra computational time and increase variances of DOA estimates. In [166–168], the effect of unknown correlated noise is alleviated by the covariance differencing technique. The instrumental variables based approach is proposed in [169,170]. This technique relies on the assumption that the emitter signals are temporally correlated with correlation time significantly longer than that of the noise. Other solutions include exploitation of prior knowledge of signals [171] or specific array configurations [172]. In [171], the signal waveform is expressed as a linear combination of known basis functions. This assumption is reasonable in applications like radar and active sonar. The algorithm developed therein is a good example showing that knowledge of the spatially colored noise can be traded against alternative a priori information about signals.

3.14.8.4 Beamspace processing

The computational complexity for DOA estimation grows rapidly with data dimension, i.e., the number of sensors. In many applications like radar, arrays may have thousands of elements [4,173]. Methods for reducing the data dimension without loss of information are important to these scenarios. Motivated by the idea of beamforming, the beamspace processing employs a linear transformation to the outputs of the full sensors of the array

(14.114)

where is an orthonormal transformation matrix. The columns of correspond to beamformers within a narrow DOA sector. The design of the transformation matrix is achieved by maximizing the average signal-to-noise ratio [174], selection of spatial sector [175] or minimizing error variances [176]. The beamspace processing may improve estimation performance by filtering out interferences outside the sector of interest and relax the assumption of white noise to local whiteness. As indicated in [177,178], the resolution threshold of the MUSIC algorithm can be lowered in beamspace. With prior knowledge on the true DOA parameter, it is possible to theoretically attain the Crámer-Rao bound by proper choice of the transformation matrix [176].

The adoption of beamspace processing into MUSIC and ESPRIT algorithms is addressed in [179] and references therein. It is interesting to observe that the array response vector becomes after the transformation (14.114). This allows a simpler expression of array manifold vector and facilitates the application of root-MUSIC and ESPRIT in the 2D case [180]. As pointed out in [180], beamspace transformation has a close link to array interpolation. The interpolated array scheme proposed by Friedlander and Weiss [38] employs a linear transformation to map the manifold vectors for an arbitrary array onto ULA-type response vectors. The field of view of the array is divided into L sectors, defined by . Then a set of angles is selected for each sector,

(14.115)

Let and denote the array response matrix of the real array and the virtual array with desired response, respectively. An interpolation matrix is computed for each sector as the least square solution such that is minimized. One may use a weighted least square formulation to improve interpolation accuracy. In [181], an MSE design criterion is suggested to reduce DOA estimation bias caused by array interpolation. An interesting observation is the duality between array interpolation and coherent signal space averaging introduced in Section 3.14.6.2. The former designs the mapping matrix based on the spatially sampled frequencies, while the latter based on samples in the temporal frequency domain. Both techniques are useful for increasing applicability of computationally efficient subspace methods.

3.14.8.5 Distributed sources

In several array processing applications, such as radio communications, underwater acoustics and radar, physical measurements show that the effects of angle spread should be taken into account in the modeling. This appears in wireless communications, for example, an elevated base station experiences the received signal as distributed in space due to local scattering around the mobile [182,183]. The array output in distributed source modeling can be expressed as , where describes the contribution of the ith signal to the array output. Unlike in the point source modeling where , the source energy is spread over some angular volume and is written as [184–186]

(14.116)

where is the angular signal density of the ith source, contains location parameters of the ith source and is the angular field of view. Examples for are the two bounds of a uniformly distributed source or mean and standard deviation of source with Gaussian angular distribution. The problem of interest here is to estimate the unknown parameter vector .

For small angular spread, the distributed source modeling (14.116) usually leads to a signal covariance matrix of the form

(14.117)

where the matrix is a fully occupied matrix with elements depending on the array shape and signal distribution. As a result, the rank of the signal covariance matrix is equal to the number of sensors M. This implies that a separation between signal subspace and noise subspace is not possible. To overcome this difficulty, a number of approaches based on subspace methods have been suggested. In [187], the signal subspace is approximated by eigenvectors associated with dominant eigenvalues. In [185,186], a generalized subspace in Hilbert space is defined to preserve the eigenstructure as in the point source modeling. Based on an approximation of the signal covariance matrix, a root-MUSIC algorithm is derived in [188]. In [189], the property of the inverse of the covariance matrix is exploited to establish the orthogonality between signal and noise subspace. Performance bounds and analysis of subspace methods in the context of distributed sources are considered in [190,191].

Note that the distributed source modeling also affects the design of the adaptive beamformer as the distortionless constraint (14.27) no longer holds. In [185], a generalized minimum variance beamformer is proposed by considering total distributed energy of the signal. The resolution of [185] is found superior to [186–188] in simulation. While the above mentioned methods are mostly semiparametric, parametric methods based on ML approach and covariance matching techniques are derived in [97] and [94], respectively. Through the application of the extended invariance principle, the high computational complexity often encountered by the parametric approach is significantly lowered in [94].

3.14.8.6 Polarization sensitivity

Most direction finding algorithms presented before consider sensor arrays in which the output of each sensor is a scalar response to, for example, acoustic pressure or one component of the electric or magnetic fields. As the array manifold depends only on the direction of arrival, one is able to retrieve the spatial signature of the emitting signals without estimating polarization parameters. Polarization is an important property of electromagnetic waves. In wireless communications, polarization diversity has played a key in antenna design [192]. The transverse components of the electric or magnetic fields are related through polarization parameters. Due to this additional information, the DOA estimation performance can be improved by polarization sensitive antenna arrays. In [193], an extension of MUSIC is suggested for polarization sensitive arrays. The subspace fitting method, ML based approach and ESPRIT algorithm were developed for diversely polarized signals [61,194–199], respectively. A performance study can be found in [200,201].

A complete data model for vector sensors that characterizes all six components of the electromagnetic fields is suggested in [202]. Therein, it is shown that in contrast to scalar sensor arrays, DOA estimation is possible using only one single vector sensor. Identifiability and uniqueness issues related to vector sensors have been investigated in [203,204]. Other interesting applications including seismic localization, acoustics, and biomedical engineering have been discussed in [205–208].

• See Vol. 1, Chapter 4 Random Signals and Stochastic Processes

• See Vol. 1, Chapter 11 Parametric Estimation

• See this Volume, Chapter 2 Model Order Selection

• See this Volume, Chapter 8 Performance Analysis and Bounds