1
$\begingroup$

I have a discrete datastream of length $10^5$ samples. Somewhere embedded in it is a rectangular pulse of unknown amplitude (prior probability of data containing signal is 0.5) and width 100 samples. I need to be able to detect this, so I think my statistical model should be:

\begin{align} \mathcal H_0 &: Y_i = W_i \sim \mathcal{N}(0,1) \\ \mathcal H_1 &: Y_i = W_i + A\big(H[p] - H[p-100]\big)\sim \mathcal{N}\bigg(A\big(H[p] - H[p-100]\big), 1\bigg) \end{align}

where $H[p]$ is the Heaviside function, and $p$ is unknown, but can be distributed uniformly over the sample length. I need to construct a Neyman-Pearson statistic from this model, but I'm unsure how to proceed. Any suggestions? Thanks in advance.

Edit 1: I am looking for an approach that requires $\mathcal{O}(N)$ or $\mathcal{O}(N\ln{N})$ operations, so my first guess is I should be able to reduce the test statistic, or at least be able to evaluate it, in a convolution sum/integral over the data. Also, the prior of $1/2$ implies that roughly 50% of the time all such operations are in vain (especially the moving average approach), so I need an computationally effective way to detect this.

$\endgroup$
  • $\begingroup$ In the end, I need to deduce a scalar from the data and compare it to the threshold (CFAR). A moving average is fine, but it does not provide me with a scalar quantity in the end. Sorry if I missed your point. $\endgroup$ – Razor Jul 2 at 22:31
1
$\begingroup$

I'd suggest trying to get rid of the $p$ index. You can write $\mathcal H_1$ as $Y_i = W_i + A$, then you can do the detection on each sample. You put the self-study tag, so I'll let you do the math but it'll come down to detecting the pulse if $y_i > \frac{A}{2}$. This will only work, if you know $A$ of course. You'll need a fairly high SNR for this to work well though. If the pulse is more obscured by the noise, you can try the next approach.

Another way to approach this problem, is to use filtering. Since you know you're looking for a rectangular pulse of length $100$, you can run the noisy data through a matched filter which will at least give you some processing gain (https://ccrma.stanford.edu/~jos/sasp/Processing_Gain.html). If you plot the samples after the filtering, you'll see a peak somewhere. Since the matched filter will have some delay, the start of the pulse is $\text{Peak Index}-\text{Pulse length}+1$. This is another way to do the processing, especially if you are able to gather a batch of data then do the processing.

Edit

The first approach requires a single scan through the input data stream leading to $10^5$ comparisons, $\mathcal{O}(N)$ operations where $N$ is the length of the input data.

The second approach involves using a FIR filter which can be done in $\mathcal{O}(NM)$, where $M$ is the length of the filter.

The second approach can also be implemented using FFT filtering which can be done in $\mathcal{O}(N\text{ log}N)$ operations.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I tried this, and also the moving average, but either of those approaches require $\mathcal{O}(N^2)$ operations. I need to do it in at least $\mathcal{O}(N)$ or $\mathcal{O}(N\ln{N})$ operations. Maybe I should have mentioned this in the question, I will edit it. $\endgroup$ – Razor Jul 2 at 22:26

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.