next up previous
Next: About this document Up: No Title Previous: No Title

Computer assignment 1

Neyman-Pearson detection and stationary time series data

The aims of this assignment are the following: I would recommend that you use MATLAB for all computer assignments (although if you are very familiar with some other package and MATLAB leaves a bad taste in your mouth, I will be sympathetic). Don't write any code that you don't have to (ever!) - if you can find a reliable source that provides you with the required functionality, then use it (at your own peril, of course).

Throughout this project you will require data and routines which can be obtained via HTTP from tex2html_wrap_inline204 nicolls/eee515z/comass1. You can get them from me if you can't find a browser.

I expect a report from you detailing the results and conclusions you have reached. Don't hand back reams of code - a brief outline of the algorithm used in the implementations is more than sufficient. Results must be presented for sensible and interesting cases; analytical derivations must be precise and complete. Insightful comments and shattering observations will be more than appreciated.

1. Random vector generator
Write a function which generates random sample vectors from a normal distribution tex2html_wrap_inline206 . At the very least, the function should take the vector tex2html_wrap_inline208 and the matrix tex2html_wrap_inline210 as parameters. The dimensionality of the random vectors returned should be determined by the dimensions of these two parameters.

Test you function for the 2-D case. Consider a covariance matrix of the form


for some tex2html_wrap_inline214 and some tex2html_wrap_inline208 , and generate a number of samples from this distribution. Plot these on a scatter diagram and confirm that you get what you expect.

2. Detection in white noise
Design a UMP Neyman-Pearson test for detecting the signal tex2html_wrap_inline218 in white Gaussian noise with power tex2html_wrap_inline220 . Use the principle of sufficiency to reduce the dimensionality of the detection statistic. Find the power of the test as a function of the false alarm probability tex2html_wrap_inline222 and the parameter tex2html_wrap_inline224 .

Use the signal tex2html_wrap_inline226 from the web page to experimentally verify your results for say 10 sensible values of tex2html_wrap_inline228 and tex2html_wrap_inline230 . Do this by generating tex2html_wrap_inline232 random samples from the relevant distributions and finding the average detection rate. Check that the false alarm rate is also as expected.

3. Detection with known covariance matrix
MATLAB users: fetch the files required for the random covariance matrix generator (markovcm.m and randmcm.m). Generate a random Markov covariance matrix for your use with the command

R = randmcm.

Make a note of the value of tex2html_wrap_inline234 Other users: use the already generated ascii covariance matrix R.dat for this section.
Notice that the matrix has a Toeplitz structure, i.e. it is banded in lines parallel to the main diagonal.

Suppose the signal to be detected is still tex2html_wrap_inline226 , but this time the noise is distributed tex2html_wrap_inline238 . The observed signal then has the distribution


If this signal was a sample from a stationary random process, what would the autocovariance function be? What would the autocorrelation function be under each hypothesis? The hypothesis testing problem is to test tex2html_wrap_inline240 versus tex2html_wrap_inline242 in the model above, with tex2html_wrap_inline210 the covariance matrix you have been presented with.

Analytical work: Suppose you didn't know this covariance matrix, and assumed the independent uncorrelated case tex2html_wrap_inline246 for the design of your detector. What would the actual false alarm rate that you achieve be as a function of the desired false alarm rate tex2html_wrap_inline222 that you used in the detector design? How would the detection probability be affected by the mismatch between the model and the actual data distribution? Make some plots demonstrating the effects for some particular configuration of parameters.

Experimental work: Approach the problem now from the standpoint that you do know tex2html_wrap_inline210 , and design the Neyman-Pearson detector accordingly. Find expressions for the false alarm probability and detection probability. Repeat the experiment you performed in the previous question for one of the values of tex2html_wrap_inline222 , and verify that you get what you expect. How has the correlation between the noise samples decreased the efficiency of your detector?

4. Invariant detectors
We will assume that the signal you are detecting has been distorted in two ways:

  • It may have an unknown DC offset, and
  • It may have an unknown linear trend which adds to the data sample (i.e. if the sample is tex2html_wrap_inline254 , there is a component tex2html_wrap_inline256 added to each sample point for some unknown a.
Design a UMP detector which is invariant to these unknown components for the correlated noise of the previous question. Make this derivation as general as possible; define a general linear subspace tex2html_wrap_inline260 to which you require invariance in the detection problem, and design the detector to be invariant to any signal components lying in this subspace. Does the invariance requirement in the hypothesis test seem reasonable to you?

Test your result in the following way: again for each tex2html_wrap_inline224 generate say 500 samples of noise and signal plus noise. To each of these samples add a linear trend with some offset (let the slope of the trend come from the distribution U[-1,1] and the offset from U[0,10] - it doesn't really matter; for the detector you assume you don't know this). Confirm that for some useful value of tex2html_wrap_inline222 and some interesting values of tex2html_wrap_inline224 you get what you expect.

Having done this, note the following:

  • Do you see that the detection statistic (in whichever way you have formulated this) incorporates a null-steering filter which first projects the observation into the space orthogonal to tex2html_wrap_inline260 ? For some purposes the subspace tex2html_wrap_inline260 is called the interference subspace; the detector ignores any components in this subspace by assuming them to be equivalent.
  • Notice that for this situation, we have to account for invariance before finally reducing the problem by sufficiency.
  • For the detector we assumed that we know nothing about the parameters of the interference. Yet for the simulation we had to draw these parameters from known distributions. Also, for the Neyman-Pearson formulation we assumed that we had no a priori knowledge about which hypothesis was in force when the observation was generated. Surely if we took this information into account we could construct a better detector? Do we ever know nothing about the unknown parameters? Bayesians argue that even at worst you could always put a vague prior to any parameter.

5. Detection in time-series For time-series problems, unless you have some synchronous mechanism for signalling the observation interval, you generally have a situation of detecting an instance of a signal at an unknown position in a continuous stream of sample points. The way to deal with this is usually to consider a window of the required length sliding across the data, and to perform a hypothesis test for every case. For window positions where there is some signal present which doesn't coincide with the template the hypothesis test breaks down partially, but nevertheless we can usually expect a peak in the detector statistic for the case when they do coincide.

If the (discrete) time-series is stationary, the autocovariance function is defined and the covariance matrix for any finite sample of the data has a Toeplitz structure. A natural and simple formulation follows for this case.

Generate a 512 element sample from a zero-mean stationary time-series which has the same autocovariance function as for the correlated noise you used in the previous questions (assume that the correlations are zero for all correlation lags greater than you have data for). Add a slowly varying sinusoid to this time-series (period = 512 samples), as well as a DC offset.

For some interesting values of tex2html_wrap_inline224 , perform the following tasks:

  • Add an instance of the signal tex2html_wrap_inline218 somewhere within this sample,
  • Use the same detector design for the previous question to find the value of the invariant detector statistic as a function of the window position (the sinusoidal interference is ignored up to first order by the invariance of the detector).
  • Plot this detector statistic for each tex2html_wrap_inline224 considered.
Notice how the statistic increases and reaches a peak at the position coinciding with the inserted signal. In most cases the statistic is above the threshold for a few window positions around the best match. As you lower the threshold value in the likelihood ratio test, there may be instances where you get a false alarm.

next up previous
Next: About this document Up: No Title Previous: No Title

Fred Nicolls
Mon Mar 10 11:49:10 GMT 1997