11
$\begingroup$

This is a detector problem I believe:

I am being stumped by what appears to be a simple problem. Basically, I have a band of interest. If signal energies exist within this band of interest, then I perform operation X on my signal.

My problem is that I am not sure exactly how to go about 'deciding' if a signal exists or not. In that, after I perform an FFT, I can look for peaks.

But now what?

  • Is the statistic used usually comparing this peak to the surrounding mean of the spectrum? Or is it some other statistic?
  • What statistical measure do I use to simply determine if a signal is present, and go from there?
  • How do I set this value? Simple thresholding?

EDIT Based on feedback:

For this simple case, I am assuming a tone, in white gaussian noise. What I am trying to get a handle on are:

  1. How exactly does one generated a ROC curve. Does one have to go and label all the data first, and then get the true-positive and false-positive rates for a multitude of thresholds?

  2. How does decreasing SNR affect the ROC curve? Move it towards the diagonal?

  3. What is adaptive thesholding doing to a given ROC curve that was otherwise generated without an adaptive threshold?

    3a. What are some common adaptive threshold techniques I can look at that are common?

$\endgroup$
  • $\begingroup$ Do you want a batch (offline) algorithm, or a sequential (online) one? Do you have noise and signal statistics (i.e., can you characterize the likelihood ratio)? If so, have you tried using an SPRT? $\endgroup$ – Emre Apr 19 '12 at 7:10
  • $\begingroup$ @Emre It can be offline. I am not really sure what you mean by signal/noise statistics, I have a sensor that will measure a signal (tone) in the presence of noise, and its SNR can vary... $\endgroup$ – Spacey Apr 19 '12 at 15:26
  • $\begingroup$ He means: what are the statistical properties of the noise and the signal? Do you know the distribution of the noise? What about the distribution of the signal plus noise? $\endgroup$ – Jason R Apr 19 '12 at 17:18
  • $\begingroup$ @JasonR I see. Well, the signal will be a tone, and the noise is gaussian. Am I missing something? $\endgroup$ – Spacey Apr 19 '12 at 18:05
  • $\begingroup$ Maybe. White Gaussian? The point is that in order to analyze it theoretically, you need to assume some probability model for the noise and signal plus noise. Based on that answer, you can do that. $\endgroup$ – Jason R Apr 19 '12 at 18:16
8
$\begingroup$

This is one of the oldest signal processing problems, and a simple form is likely to be encountered in an introduction to detection theory. There are theoretical and practical approaches to solving such a problem, which may or may not overlap depending upon the specific application.

A first step toward understanding the approaches to the problem is understanding how you would measure the performance of your signal presence detector. There are two important and related metrics used to quantitatively measure how good a detector is: its probability of detection $P_d$ and its probability of false alarm $P_{fa}$.

$P_d$ is specified as the probability that your detector will indicate the presence of the signal of interest, given that the signal is actually there. Conversely, $P_{fa}$ is the probability that your detector will indicate the presence of the signal of interest, given that the signal is not there. As you might expect, then, in a perfect world, we would design a system that yields $P_d = 1$ and $P_{fa} = 0$ and call it a day. As you might also expect, it's not that easy. There is an inherent tradeoff between the two metrics; typically if you do something that improves one, you will observe some degradation in the other.

A simple example: if you are looking for the presence of a pulse against a background of noise, you might decide to set a threshold somewhere above the "typical" noise level and decide to indicate presence of the signal of interest if your detection statistic breaks above threshold. Want a really low false-alarm probability? Set the threshold high. But then, the probability of detection might decrease significantly if the elevated threshold is at or above the expected signal power level!

To visualize the $P_d$ / $P_{fa}$ relationship, the two quantities are often plotted against one another on a receiver operating characteristic curve. Here's an example from Wikipedia:

enter image description here

An ideal detector would have a ROC curve that hugs the top of the plot; that is, it could provide guaranteed detection for any false alarm rate. In reality, a detector will have a characteristic that looks like those plotted above; increasing the probability of detection will also increase the false alarm rate, and vice versa.

From a theoretical perspective, therefore, these types of problems boil down to selecting some balance between detection performance and false-alarm probability. How that balance is described mathematically depends upon your statistical model for the random process that the detector observes. The model will typically have two states, or hypotheses:

$$ H_0: \text{no signal is present} $$ $$ H_1: \text{signal is present} $$

Typically, the statistic that the detector observes would have one of two distributions, according to which hypothesis is true. The detector then applies some sort of test that is used to determine the true hypothesis and therefore whether the signal is present or not. The distributions of the detection statistic is a function of the signal model that you choose as appropriate for your application.

Common signal models are the detection of a pulse-amplitude-modulated signal against a background of additive white Gaussian noise (AWGN). While that description is somewhat specific to digital communications, many problems can be mapped to that or a similar model. Specifically, if you are looking for a constant-valued tone localized in time against a background of AWGN, and the detector observes the signal magnitude, that statistic will have a Rayleigh distribution if no tone is present and a Rician distribution if one is present.

Once a statistical model has been developed, the detector's decision rule must be specified. This can be as complicated as you desire, based on what makes sense for your application. Ideally, you would want to make a decision that is optimal in some sense, based on your knowledge of the distribution of the detection statistic under both hypotheses, the probability of each hypothesis being true, and the relative cost of being wrong about either hypothesis (which I'll talk more about in a bit). Bayesian decision theory can be used as a framework for approaching this aspect of the problem from a theoretical perspective.

In the simplest practical case, the detector might trigger a detection if the detection statistic exceeds a fixed threshold $T$. In a more complicated and practical case, the detector might have some criteria for setting an adaptive threshold $T(t)$ and trigger a detection at time $t$ if the detection statistic breaks the threshold value at that instant. In your description of your problem, you hit on one common method for setting such an adaptive threshold: calculate the neighborhood mean to estimate the "background level", then set a detection threshold some amount above that mean. This can work for some applications, and there are many other ways to arrive at such a threshold.

Given a statistical model for the detector's input and the decision rule used to map that statistic to detection conclusions, one can then calculate the detector's theoretical performance metrics. In the design phase, you would typically calculate these metrics as functions of the free design parameters that you have (for instance, the threshold $T$ above). You can then evaluate the inherent tradeoffs: "if I set $T=5$, then I get $P_d = 0.9999$, but $P_{fa} = 0.01$. That's too high of a false alarm rate, so I better increase the threshold."

Where you eventually decide to sit on the performance curve is up to you, and is an important design parameter. The right performance point to choose depends upon the relative cost of the two types of possible failures: is it worse for your detector to miss an occurrence of the signal when it happens or to register an occurrence of the signal when it hasn't happened? An example: a fictitious ballistic-missile-detector-with-automatic-strikeback-capability would be best served to have a very false alarm rate; starting a world war because of a spurious detection would be unfortunate. An example of the converse situation would be a communication receiver used for safety-of-life applications; if you want to have maximum confidence that it doesn't fail to receive any distress messages, it should have a very high probability of detection of the transmitted signal.

$\endgroup$
  • $\begingroup$ Thanks JasonR, very nice post. I am still digesting your post, however one question comes to mind. How exactly is this ROC curve being generated? I understand that I measure true-positive and false-positive rate for any classifier, and that marks one point in the ROC curve. So what is being changed such that I get many points so that I can generate a curve for any one classifier? $\endgroup$ – Spacey Apr 19 '12 at 17:44
  • 1
    $\begingroup$ The ROC will typically be valid for a single set of operating conditions of your system (e.g. signal-to-noise ratio). For design purposes, you can characterize your system for a worst-case scenario (e.g. minimum SNR) to ensure that it still meets requirements. The curve is traced out by adjusting the free parameters that you have in designing your detector (e.g. the threshold level). As you adjust those detector parameters, $P_d$ and $P_{fa}$ will change accordingly, tracing out the curve. $\endgroup$ – Jason R Apr 20 '12 at 3:57
1
$\begingroup$

The statistic is the likelihood ratio (LR), and the test is comparison of the LR against a threshold. If you follow the tradition of placing the likelihood of the null hypothesis in the denominator, you decide in favor of the alternative hypothesis (against the null hypothesis) if the LR is sufficiently high. The higher the ratio, the greater your confidence. This is the test you would perform if you have already collected the data. If you want to decide as the data arrives piece-meal, you can use a sequential test, like SPRT.

At this stage you might benefit from a book on hypothesis testing or decision theory (more general).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.