Spectral Detection 1.2 2003/05/30 2003/08/29 16:01:53.976 GMT-5 Don Johnson dhj@rice.edu Don Johnson dhj@rice.edu Eileen Krause erkrause@rice.edu Kyle Clarkson kclarks@rice.edu Elizabeth Gregory lizzardg@rice.edu Kevin Duh kevinduh@rice.edu Mariyah Poonawala mariyah@rice.edu Matthew Jeanes mjeanes@rice.edu Jeffrey Silverman jsilv@rice.edu From the results presented in the previous sections, the colored noise problem was found to be pervasive, but required a computationally difficult detector. The simplest detector structure occurs when the additive noise is white; this notion leads to the idea of whitening the observations, thereby transforming the data into a simpler form (as far as detection theory is concerned). However, the required whitening filter is often time-varying and can have a long-duration unit-sample response. Other, more computationally expedient, approaches to whitening are worth considering. An only slightly more complicated detection problem occurs when we have a diagonal noise covariance matrix, as in the white noise case, but unequal values on the diagonal. In terms of the observations, this situation means that they are contaminated by noise having statistically independent, but unequal variance components: the noise would thus be non-stationary. Few problems fall directly into this category; however, the colored noise problem can be recast into the white, unequal-variance problem by calculating the discrete Fourier Transform (DFT) of the observations and basing the detector on the resulting spectrum. The resulting spectral detectors greatly simplify detector structures for discrete-time problems if the qualifying assumptions described in sequel hold. Let W be the so-called × L L "DFT matrix" W 1 1 1 … 1 1 W W 2 … W L 1 1 W 2 W 4 … W 2 L 1 ⋮ ⋮ ⋮ ⋮ ⋮ 1 W L 1 W 2 L 1 … W L 1 L 1 where W is the elementary complex exponential 2 L . The discrete Fourier Transform of the sequence r l , usually written as R k l 0 L 1 r l 2 l k L , can be written in matrix form as R W r . To analyze the effect of evaluating the DFT of the observations, we describe the computations in matrix form for analytic simplicity. The first critical assumption has been made: take special note that the length of the transform equals the duration of the observations. In many signal processing applications, the transform length can differ from the data length, being either longer or shorter. The statistical properties developed in the following discussion are critically sensitive to the equality of these lengths. The covariance matrix K R of R is given by W K r W . Symmetries of these matrices - the Vandermonde form of W and the Hermitian, Toeplitz form of K r - leads to many simplifications in evaluating this product. The entries no the main diagonal are given by The curious index l 1 on the matrix arises because rows and columns of matrices are traditionally indexed beginning with one instead of zero. K R K K l L 1 L 1 L l K 1 , | l | + 1 r 2 l k L The variance of the k th term in the discrete Fourier Transform of the noise thus equals the discrete Fourier Transform of the windowed covariance function. This window has a triangular shape; colloquially termed the "rooftop" window, its technical name is the Bartlett window and it occurs frequently in array processing and spectral estimation. We have found that the variance equals the smoothed noise power spectrum evaluated at a particular frequency. The off-diagonal terms of K R are not easily written; the complicated result is k 1 k 2 k 1 k 2 K R k 1 k 2 l 0 L 1 K 1 , l + 1 r -1 k 1 k 2 1 l k 1 k 2 L k 1 k 2 L 2 l k 1 L 2 l k 2 L The complex exponential terms indicate that each off-diagonal term consists of the sum of two Fourier Transforms: one at the frequency index k 2 and the other negative index k 1 . In addition, the transform is evaluated only over non-negative lags. The transformed quantity again equals a windowed version of the noise covariance function, but with a sinusoidal window whose frequency depends on the indices k 1 and k 2 . This window can be negative-valued! In contrast to the Bartlett window encountered in evaluating the on-diagonal terms, the maximum value achieved by the window is not large ( 1 k 1 k 2 L compared to L). Furthermore, this window is always zero at the origin, the location of the maximum value of any covariance function. The largest magnitudes of the off-diagonal terms tend to occur when the indices k 1 and k 2 are nearly equal. Let their difference be one; if the covariance function of the noise tends toward zero well within the number of observations, L, then the Bartlett window has little effect on the covariance function while the sinusoidal window greatly reduces it. This condition on the covariance function can be interpreted physically: the noise in this case is wideband and any correlation between noise values does not extend over significant portion of the observation record. On the other hand, if the width of the covariance function is comparable to L, the off-diagonal terms will be significant. This situation occurs when the noise bandwidth is smaller than or comparable to the reciprocal of the observation interval's duration. This condition on the duration of the observation interval relative to the width of the noise correlation function forms the second critical assumption of spectral detection. The off-diagonal terms will thus be much smaller than corresponding terms on the main diagonal ≪ K R k 1 k 2 2 K R k 1 k 1 K R k 2 k 2 . In the simplest case, the covariance matrix of the discrete Fourier Transform of the observations can be well approximated by a diagonal matrix. K R σ 0 2 0 … 0 0 σ 1 2 0 ⋮ ⋮ 0 ⋱ 0 0 … 0 σ L - 1 2 The non-zero components σ k 2 of this matrix constitute the noise power spectrum at the various frequencies. The signal component of the transformed observations R is represented by S i , the DFT of the signal s i , while the noise component has this diagonal covariance matrix structure. In the frequency domain, the colored noise problem can be approximately converted to a white noise problem where the components of the noise have unequal variances. To recap, the critical assumptions of spectral detection are The transform length equals that of the observations. In particular, the observations cannot be "padded" to force the transform length to equal a "nice" number (like a power of two). The noise's correlation structure should be much less than the duration of the observations. Equivalently, a narrow correlation function means the corresponding power spectrum varies slowly with frequency. If either condition fails to hold, calculating the Fourier Transform of the observations will not necessarily yield a simpler noise covariance matrix. The optimum spectral detector computes, for each possible signal, the quantity R K R S i S i K R S i 2 The real part in the statistic emerges because R and S i are complex quantities.. Because of the covariance matrix's simple form, this sufficient statistic for the spectral detection problem has the simple form R K R S i 1 2 S i K R S i k 0 L 1 R k S i k σ k 2 1 2 S i k 2 σ k 2 Each term in the dot product between the discrete Fourier Transform of the observations and the signal is weighted by the reciprocal of the noise power spectrum at that frequency. This computation is much simpler than the equivalent time domain version and, because of algorithms such as the fast Fourier Transform, the initial transformation (the multiplication by W or the discrete Fourier Transform) can be evaluated expeditiously. Sinusoidal signals are particularly well-suited to the spectral detection approach. If the signal's frequency equals one of the analysis frequencies in the Fourier Transform ( ω 0 2 k L for some k), then the sequence S i k is non-zero only at this frequency index, only one term in the sufficient statistic's summation need be computed, and the noise power is no longer explicitly needed by the detector (it can be merged into the threshold). R K R S i 1 2 S i K R S i R k S i k σ k 2 1 2 S i k 2 σ k 2 If the signal's frequency does not correspond to one of the analysis frequencies, spectral energy will be maximal at the nearest analysis frequency but will extend to nearby frequencies also. This effect is termed "leakage" and has been well studied. Exact formulation of the signal's DFT is usually complicated in this case; approximations which utilize only the maximal-energy frequency component will be sub-optimal (i.e., yield a smaller detection probability). The performance reduction may be small, however, justifying the reduced amount of computation.