2
$\begingroup$

In python I'm creating a simple matched filter to find a feature $Q$ in a time-series $T$ where $$|Q| \ll |T|.$$

I've got it working like this:

np.flip(q)

matched_filter_output = convolve(t, q, mode='same')
peaks, _ = find_peaks(matched_filter_output)
# thresholding and finding of possible matches...

My question is whether the line np.flip(q) is really required.

To me it works both ways equally well. When I plot a simple example using whole numbers for $Q$ and $T$, all the flipping does is to flip the values around the peaks, with the peaks remaining in the same place.

Also the docs state that np.convolve() flips its second argument anyway. So basically which is more correct? to implement a matched filter do I flip Q before calling np.convolve() or not?

Also what's a good citation I can use for this technique? The only recent article which I could find which breaks down the discrete case clearly using convolution is this one.

$\endgroup$
5
  • $\begingroup$ Is your $q$ symmetric and real? If so, the matched filter can be implemented with convolution the way you have it and you'll get basically the same result as if you flip (and conjugate) $q$ (which is what the match filter would technically require). But for other signal types, this won't work, as detailed in my answer. $\endgroup$
    – Gillespie
    Commented Jun 13 at 15:12
  • $\begingroup$ The values are real and Q is not symmetrical. $\endgroup$
    – pnadeau
    Commented Jun 13 at 15:47
  • $\begingroup$ Is $t$ basically symmetric? I think that would have the same effect. $\endgroup$
    – Gillespie
    Commented Jun 13 at 15:53
  • $\begingroup$ Neither T nor Q are symmetric. Both are real. I am using a MF to find multiple non-overlapping instances of the feature Q in a longer time series T. $\endgroup$
    – pnadeau
    Commented Jun 13 at 16:17
  • $\begingroup$ You can even use match filtering to find multiple partially overlapping instances of Q in T. The centers of the instances of Q in T only need to be separated by ~1/(bandwidth of Q) in order to distinguish them after match filtering, so they can overlap quite a bit. $\endgroup$
    – Gillespie
    Commented Jun 13 at 16:27

2 Answers 2

1
$\begingroup$

Yes, in general you need the flip (though if your signal is symmetric it won't matter), and if your signals are complex you need to conjugate $q$ as well. The matched filter is the cross correlation of one signal with another. We often implement it with convolution, which is a related operation, but not identical.

The difference between cross correlation and convolution is that convolution flips $q$ and cross correlation doesn't. Therefore, to perform cross correlation via convolution, we pre-flip the signal ($q$) to undo the flipping applied in convolution. If our signals are complex, cross correlation also conjugates $q$, which convolution does not. So the total operation to implement cross correlation via convolution in Python is:

matched_filter_output = np.convolve(t, np.flip(np.conj(q)), mode='same')

Why cross correlation?

One question that arises is, why does the matched filter use cross correlation instead of basic convolution (without the flipping and conjugating)? One way to see the ideal nature of cross correlation for matched filtering is to look at the derivation of the matched filter. This derivation shows that cross correlating a signal ($t$ in your nomenclature) with the signal of interest (your $q$) achieves the maximum SNR for Gaussian noise.

Another way to see this is to consider that we are effectively trying to "undo" the fact that our signal of interest has been convolved with something else already. For example, we may send a signal through a noisy channel (or in an imaging application, a "scene"), and in the process our signal is effectively convolved with the channel impulse response.

Ideally we would like to invert this convolution. But the inverse of convolution does not necessarily exist. So mathematically, the closest approximation to an inverse that is guaranteed to exist is an adjoint (see my answer here for practical details on that). It turns out that cross correlation is the adjoint of convolution. This is why it is used in the matched filter.

Why is cross correlation implemented with convolution?

So why do we implement our desired operation (cross correlation) with another (convolution)? The reason is that convolution can be implemented efficiently via FFTs (see many questions and answers on this site, such as this one). The process is roughly:

  1. Compute $L = N + M - 1$, where $N$ is the length of $t$ and $M$ is the length of $q$
  2. Zero pad $t$ and $q$ to length $L$
  3. Compute the FFT of the zero padded $t$ and $q$
  4. Perform element-wise multiplication of the FFTed signals
  5. Take the IFFT of the result of step 4

This is much more efficient than performing convolution directly since it takes advantage of the efficiency of the FFT and converts convolution to point-wise multiplication in the frequency domain.

Summary

In summary, the matched filter is a cross correlation operation, not a convolution, because cross correlation maximizes SNR. We can implement cross correlation via convolution if we flip and conjugate one of the signals. The reason we implement cross correlation via convolution is because convolution can be performed more efficiently via FFTs.

$\endgroup$
1
$\begingroup$

In general, one must "flip" and conjugate the waveform to be filtered to yield the matched filter. Related to this, there is some misunderstanding about viewing the convolution as flipping one of the signals, which this answer goes over. Viewing the flipping of the signal to yield the matched filter is a little more intuitively satisfying since it is a direct time-reversal, but that's just my opinion.

You can get away with not flipping (nor conjugating) depending on what your signal is. Take the example where the signal is a simple rectangular pulse, which is symmetric and real:

enter image description here

In this case, there is no need to flip or conjugate the signals since they give the same answer:

enter image description here

Now if your signal was something like, a linear frequency chirp:

enter image description here

Then you must time-reverse and conjugate the input signal to yield the matched filter:

enter image description here

The top output is the correct one. If you're planning on writing a function for matched filtering, you must always time-reverse and conjugate the signal.

In the case of having multiple chirps, define the matched filter $h(t) = x^*(-t)$, where $x(t)$ is the expression for the chirp itself. Now consider we have the following signal composed of three chirps:

enter image description here

Then match-filtering this signal you will get three peaks, as expected:

enter image description here

$\endgroup$
3
  • $\begingroup$ Good illustrations. Now here's a stupid question: can I still use the matched filter to find multiple non-overlapping chirps in a longer time-series? $\endgroup$
    – pnadeau
    Commented Jun 13 at 16:13
  • $\begingroup$ @pnadeau Of course, that is inherently part of what the matched filter does. Its output will peak at the delays corresponding to the location of each desired signal. I've made an update to the post. $\endgroup$
    – Envidia
    Commented Jun 13 at 16:35
  • 1
    $\begingroup$ Thanks for your detailed answer. In the end it went to @Gillespie but I wish I could give two checkmarks. $\endgroup$
    – pnadeau
    Commented Jun 13 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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