67 Detection: Determining the Number of Sources

Williams, D.B. “Detection: Determining the Number of Sources” Digital Signal Processing Handbook Ed. Vijay K. Madisetti and Douglas B. Williams Boca Raton: CRC Press LLC, 1999 c 1999 by CRC Press LLC 67 Detection: Determining the Number of Sources Douglas B. Williams Georgia Institute of Technology 67.1 Formulation of the Problem 67.2 Information Theoretic Approaches AIC and MDL EDC 67.3 Decision Theoretic Approaches The Sphericity Test Multiple Hypothesis Testing 67.4 For More Information References The processing of signals received by sensor arrays generally can be separated into two problems: (1) detecting the number of sources and (2) isolating and analyzing the signal produced by each source. Wemakethisdistinctionbecausemanyofthealgorithmsforseparatingandprocessingarray signals make the assumption that the number of sources is known a priori and may give misleading results if the wrong number of sources is used [3]. A good example are the errors produced by many high resolution bearing estimation algorithms (e.g., MUSIC) when the wrong number of sources is assumed. Because, in general, it is easier to determine how many signals are present than to estimate the bearings of those signals, signal detection algorithms typically can correctly determine thenumberofsignalspresentevenwhenbearingestimationalgorithmscannotresolvethem. Infact, thecapabilityofanarraytoresolvetwocloselyspacedsourcescouldbesaidtobelimitedbyitsability to detect that there are actually two sources present. If we have a reliable method of determining the number of sources, not only can we correctly use high resolution bearing estimation algorithms, but we can also use this knowledge to utilize more effectively the information obtained from the bearing estimation algorithms. If the bearing estimation algorithm gives fewer source directions than we know there are sources, then we know that there is more than one source in at least one of those directions and have thus essentially increased the resolution of the algorithm. If analysis of the information provided by the bearing estimation algorithm indicates more source directions than we know there are sources, then we can safely assume that some of the directions are the results of false alarms and may be ignored, thus decreasing the probability of false alarm for the bearing estimation algorithms. Inthissectionwewillpresentanddiscussthemorecommonapproachestodetermining the number of sources. 67.1 Formulation of the Problem The basic problem is that of determining how many signal producing sources are being observed by an array of sensors. Although this problem addresses issues in several areas including sonar, radar, c 1999 by CRC Press LLC communications, and geophysics, one basic formulation can be applied to all these applications. We will give only a basic, brief description of the assumed signal structure, but more detail can be found in references such as the book by Johnson and Dudgeon [3]. We will assume that an array of M sensors observes signals produced by Ns sources. The array is allowed to have an arbitrary geometry. For our discussion here, we will assume that the sensors are omnidirectional. However, this assumption is only for notational convenience as the algorithms to be discussed will work for more general sensor responses. The output of the mth sensor can be expressed as a linear combination of signals and noise X ym.t/ D si .t −1i.m//Cnm.t/ : iD1 The noise observed at the mth sensor is denoted by nm.t/. The propagation delays, 1i.m/, are measured with respect to an origin chosen to be at the geometric center of the array. Thus, si.t/ indicates the ith propagating signal observed at the origin, and si.t − 1i.m// is the same signal measuredbythemthsensor. Foraplanewaveinahomogeneousmedium, thesedelayscanbefound from the dot product between a unit vector in the signal’s direction of propagation, o, and the sensor’s location, xEm, 1i.m/ D i xEm ; where c is the plane wave’s speed of propagation. Most algorithms used to detect the number of sources incident on the array are frequency domain techniques that assume the propagating signals are narrowband about a common center frequency, !o. Consequently, after Fourier transforming the measured signals, only one frequency is of interest and the propagation delays become phase shifts Ym !o D XSi !oe−j!o1i.m/ CNm !o : iD1 The detection algorithms then exploit the form of the spatial correlation matrix, R, for the array. The spatial correlation matrix is the M M matrix formed by correlating the vector of the Fourier transforms of the sensor outputs at the particular frequency of interest Y D Y0 !o Y1 !o T M−1 If the sources are assumed to be uncorrelated with the noise, then the form of R is R D EYY0 D Kn CSCS0; where Kn is the correlation matrix of the noise, S is the matrix whose columns correspond to the vector representations of the signals, S0 is the conjugate transpose of S, and C is the matrix of the correlations between the signals. Thus, the matrix S has the form 2 e−j!o11.0/ S D 6 : e−j!o11.M−1/ e−j!o1Ns .0/ 3 : 7 : e−j!o1Ns .M−1/ If we assume that the noise is additive, white Gaussian noise with power n and that none of the signals are perfectly coherent with any of the other signals, then Kn D nIm, C has full rank, and the form of R is R D 2IM CSCS0 : (67.1) c 1999 by CRC Press LLC We will assume that the columns of S are linearly independent when there are fewer sources than sensors, which is the case for most common array geometries and expected source locations. As C is of full rank, if there are fewer sources than sensors, then the rank of SCS0 is equal to the number of signals incident on the array or, equivalently, the number of sources. If there are Ns sources, then SCS is of rank Ns and its Ns eigenvalues in descending order are 1, 2, , Ns . The M eigenvalues ofnIM areallequalton, andtheeigenvectorsareanyorthonormalsetoflengthM vectors. Sothe eigenvectors of R are the Ns eigenvectors of SCS plus any M −Ns eigenvectors which complete the orthonormalset,andtheeigenvaluesindescendingorderare2 C1,,2 CNs ,2,,2. The correlation matrix is generally divided into two parts: the signal-plus-noise subspace formed by the largest eigenvalues (2 C1; ; 2 CNs ) and their eigenvectors, and the noise subspace formed by the smallest, equal eigenvalues and their eigenvectors. The reason for these labels is obvious as the space spanned by the signal-plus-noise subspace eigenvectors contains the signals and a portion of the noise while the noise subspace contains only that part of the noise that is orthogonal to the signals[3]. Iftherearefewersourcesthansensors, thesmallestM −Ns eigenvaluesof R areallequal and to determine exactly how many sources there are, we must simply determine how many of the smallest eigenvalues are equal. If there are not fewer sources than sensors (Ns M), then none of the smallest eigenvalues are equal. The detection algorithms then assume that only the smallest eigenvalue is in the noise subspace as it is not equal to any of the other eigenvalues. Thus, these algorithms can detect up to M − 1 sources and for Ns M will say that there are M − 1 sources as this is the greatest detectable number. Unfortunately, all that is usually known is R, the sample correlation matrix, which is formed by averaging N samples of the correlation matrix taken from the outputs of the array sensors. As R is formed from only a finite number of samples of R, the smallestM−Ns eigenvaluesofR aresubjecttostatisticalvariationsandareunequalwithprobability one [4]. Thus, solutions to the detection problem have concentrated on statistical tests to determine how many of the eigenvalues of R are equal when only the sample eigenvalues of R are available. Whenperformingstatisticaltestsontheeigenvaluesofthesamplecorrelationmatrixtodetermine the number of sources, certain assumptions must be made about the nature of the signals. In array processing, both deterministic and stochastic signal models are used depending on the application. However, for the purpose of testing the sample eigenvalues, the Fourier transforms of the signals at frequency !o; Si.!o/, i D 1; :::; Ns; are assumed to be zero mean Gaussian random processes that are statistically independent of the noise and have a positive definite correlation matrix C. We also assume that the N samples taken when forming R are statistically independent of each other. With these assumptions, the spatial correlation matrix is still of the same form as in (67.1), except that now we can more easily derive statistical tests on the eigenvalues of R. 67.2 Information Theoretic Approaches We will see that the source detection methods to be described all share common characteristics. However, we will classify them into two groups—information theoretic and decision theoretic approaches—determined by the statistical theories used to derive them. Although the decision theoretic techniques are quite a bit older, we will first present the information theoretic algorithms as they are currently much more commonly used. 67.2.1 AIC and MDL AIC and MDL are both information theoretic model order determination techniques that can be used to test the eigenvalues of a sample correlation matrix to determine how many of the smallest eigenvalues of the correlation matrix are equal. The AIC and MDL algorithms both consist of minimizing a criterion over the number of signals that are detectable, i.e., Ns D 0; :::; M − 1. c 1999 by CRC Press LLC To construct these criteria, a family of probability densities, f.Yj.Ns//, Ns D 0; :::; M − 1, is needed, where , which is a function of the number of sources, Ns, is the vector of parameters needed for the model that generated the data Y. The criteria are composed of the negative of the log-likelihood function of the density f.Y.Ns//, where .Ns/is the maximum likelihood estimate of for Ns signals, plus an adjusting term for the model dimension. The adjusting term is needed because the negative log-likelihood function always achieves a minimum for the highest dimension model possible, which in this case is the largest possible number of sources. Therefore, the adjusting term will be a monotonically increasing function of Ns and should be chosen so that the algorithm is able to determine the correct model order. AIC was introduced by Akaike [1]. Originally, the “IC” stood for information criterion and the “A” designated it as the first such test, but it is now more commonly considered an acronym for the “Akaike Information Criterion.” If we have N independent observations of a random variable with probability density g.Y/ and a family of models in the form of probability densities f.Yj/ where is the vector of parameters for the models, then Akaike chose his criterion to minimize Z Z I.gI f.j// D g.Y/lng.Y/dY − g.Y/lnf.Yj/dY (67.2) which is known as the Kullback-Leibler mean information distance. 1 AIC./ is an estimate of −Ef g.Y/lnf.Yj/dYg and minimizing AIC./ over the allowable values of should minimize (67.2). The expression for AIC./ is h i AIC./ D −2ln f Yj .Ns/ C2 ; where is the number of independent parameters in . Following AIC, MDL was developed by Schwarz [6] using Bayesian techniques. He assumed that theapriori densityoftheobservationscomesfromasuitablefamilyofdensitiesthatpossessefficient estimates [7]; they are of the form f.Yj/ D exp. p.Y/−b.// : The MDL criterion was then found by choosing the model that is most probable a posteriori. This choice is equivalent to selecting the model for which h i MDL./ D −ln f Yj .Ns/ C 2lnN is minimized. This criterion was independently derived by Rissanen [5] using information theoretic techniques. Rissanennotedthateachmodelcanbeperceivedasencodingtheobserveddataandthat the optimum model is the one that yields the minimum code length. Hence, the name MDL comes from “Minimum Description Length”. For the purpose of using AIC and MDL to determine the number of sources, the forms of the log-likelihoodfunctionandtheadjustingtermshavebeengivenbyWax[8]. ForNs signalstheparameters that completely parameterize the correlation matrix R are fn; 1; ; Ns ; v1; ; vNs gwhere i andvi,i D 1; :::; Ns,aretheeigenvaluesandtheirrespectiveeigenvectorsofthesignal-plus-noise subspaceofthecorrelationmatrix. AsthevectorofsensoroutputsisaGaussianrandomvectorwith correlation matrix R and all the samples of the sensor outputs are independent, the log-likelihood function of f.Yj/ is lnf Yj2; 1; ; Ns ; v1; ; vNs D −pN .detR/−N exp −Ntr R−1b c 1999 by CRC Press LLC ... - tailieumienphi.vn