I have multiple (between 2 and 100) signals and need to determine when a significant number diverge from the rest. We're exploring machine learning techniques, but we also want tackle this as a signal processing problem and see where we get the best results.

This very informative post suggests that best results come from a weighted ensemble of techniques, including:

  • Similarity in time domain (static): Multiply in place and sum.
  • Similarity in time domain (with shift*): Take FFT of each signal, multiply, and IFFT. (matlab's xcorr)
  • Similarity in frequency domain (static**): Take FFT of each signal, multiply, and sum.
  • Similarity in frequency domain (with shift*): Multiply the two signals and take FFT. This will show if the signals share similar spectral shapes.
  • Similarity in energy (or power if different lengths)

But this is a fairly high-level outline. Can anyone point me to a more thorough discussion of these techniques, preferably with some python code or in lieu of that, some code in R?

  • 3
    $\begingroup$ Would it be possible to provide a bit more detail on what kind of "similarity" you are after? (EDIT: I mean conceptually, based on the problem you are dealing with. The kinds of things mentioned in the question could be probing different aspects of the signal or the system the signal came from). $\endgroup$ – A_A Jan 21 at 12:55
  • 1
    $\begingroup$ So, in your case, "similarity" means, "Two signals having similar values at the same time instance" (?) $\endgroup$ – A_A Jan 21 at 17:13
  • 2
    $\begingroup$ ...but the two are absolutely timed? As in, $x[n] = z[n]$ even if $x,z$ are acquired by two different devices? (I don't think so....but I thought I'd ask). Is it possible to mention the application? $\endgroup$ – A_A Jan 21 at 17:25
  • 1
    $\begingroup$ I can write some stuff on similarity but I am wondering if you are taking the difficult route. At the worst CN0, the AGC is maxed out. AGC and CN0 depend on each other.Since you choose to monitor CN0, the attacker is trying to jam.Therefore, why not cross reference fix quality/dilution of precision(s) across phones?It's much easier since it is one sampled quality.The receiver would not "complain" at all in the case of a spoof.In that case,it is the adjusted centroid of the receivers over a large enough area that should be validated. $\endgroup$ – A_A Jan 21 at 22:39
  • 1
    $\begingroup$ Also can you combine the machine learning with the signal processing? For instance, I found a neural net can very easily learn a Fourier transform, since it's a linear operation, but has a lot more trouble learning the magnitude of a Fourier transform, etc. So if you feed it both the raw signal and the magnitude and phase information, it might find things that it wouldn't easily find on its own. $\endgroup$ – endolith Jan 23 at 14:28

...best results come from a weighted ensemble of techniques...

Maybe they do, depending on the application. But each one of the similarities mentioned, is equivalent to the other at least when we are talking about signals originating from linear systems.

Cross correlation provides very good results especially if you are trying to figure out if a signal is noise or not and a very good application of that is in the rake receiver. And via the correlation's link to the Discrete Fourier Transform (DFT) that enables us to carry it out in the frequency domain we can start to see the equivalences between the given statements.

A more informative division would be between linear "metrics" and non-linear metrics. But, the field of "similarity metrics" is vast, so, it is best to start with what is known from the problem and then work towards a solution.

What I am going to do here is to talk a little bit about some metrics of similarity which you might find useful but then also write a little bit about other ways of doing the same thing that don't require the assessment of similarity as I think that that second part is closer to what you are trying to achieve (but not what you are asking directly).

On Similarity Metrics:

Cross-correlation will work fine if your signals have been consistently sampled to each other. That is, each device's sampling frequency remains absolutely stable but the relative points in time that the recording started can be varied. This will insert a delay between waveforms which is very easy to recover by doing multiple cross-correlations at different delays.

If you want to look at specific frequencies, you can either filter the signals prior to cross-correlation or use coherence.

Another thing you can try is Principal Component Analysis. To do this, pack all the signals that you receive from $N$ devices into a matrix and send it to PCA. PCA will try to decompose these signals into a smaller set of "principal" (uncorrelated) signals and will return a matrix with those elementary signals and their strengths. It does this using covariance, which is very closely related to correlation. The point here is that if all of the signals are the same, there are no "components" and the vector of strengths is going to be zero. But, if there is significant variation within the signals, the vector of strengths will start exhibiting some structure. You can then use the vector of strengths in a simple classifier that discriminates whether the indicated variation is negligible or worthy of an alarm.

Now, it might be that the sampling period of each GPS device is not stable (very likely). And this now means that if you were to put "one signal on top of another" (as if they were printed on transparency slides), it would be possible to align some peaks, but not others.

In that case, you could use Dynamic Time Warping (DTW). Imagine that you listen to a vinyl record with a lot of wow. You can remove that wow, by speeding up the recording when the record player slows down and vice versa. This is exactly what DTW does. You pass to it two signals and it returns a matrix that tells you where to slow down and where to speed up. After you apply this transformation to one of the signals, the peaks would align perfectly. The total amount of deviation in this matrix is a metric of similarity. But, DTW is not exactly fast...particularly if you have to consider $\frac{N*(N-1)}{2}$ unique combinations (because all of these metrics are symmetric) between all 2 out of $N$ signals.

On the specific application:

So, the application is a GPS interference alert. There are two use-case scenarios that I can see at the moment:

  1. GPS Jamming
    • Where the receiver cannot access the signals from the satelites because a local source is "flooding" its input with "noise".
  2. GPS Spoofing
    • Where the receiver thinks they are listening to a satellite, but actually they are listening to a loud black box that behaves like a satelite.

Since it is impossible to raise an interference alarm based solely on information available to a device, the idea is to incorporate information from other data sources (nearby devices / data) in order to confirm the "story" that the GPS receiver on this device is listening to.

How can we get a gauge on the quality of the fix on a given device?

There are two obvious choices:

  1. The Dilution of Precision
  2. The GPS Quality Indicator Field.

Between these two, the Dilution of Precision is a "softer" indicator (wider range of values) of the quality of the fix.

So, assuming that there is an infrastructure for collecting GPS data from a set of devices (like Waze or Glypmse do for example), then the following alarms can be raised:

  1. To counteract GPS Jamming:

    • Given the timestamp and the GPS Quality Indicator for a set of devices
      1. Select a point in time
      2. Select the subset of devices which have provided "bad" GPS quality data at or around a reasonable time interval around the selected point in time.
      3. Cluster the provided GPS locations in space
        • This can be done ridiculously fast
        • A Threshold is required to define which two clusters are considered apart enough. This can be discovered automatically or be set to a reasonable value. Bunches of receivers approximately 1km apart should be considered separate, for example.
      4. Assess the "size" of the "patch" of bad reception.
        • An obvious choice here would be to take the centroid of the cluster and find the furthest data point (so, one radius), or find the mean radius of the points or take their convex hull or use another more accurate algorithm that describes the points.
      5. Decide if the patch is big enough to warrant raising the alarm.
        • Obviously, lots of receivers in a short tunnel or underpass or close to tall buildings are not supposed to raise alarms.
  2. To counteract GPS Spoofing:

    • This is much more challenging because the problem there is to identify an unjustifiable deviation. This assumes that you have some way of knowing what is "correct" and that is the key difficulty. The easiest thing to tackle here is the GPS being spoofed over a wide area (more than one device).
    • In this case, you want to identify a cluster of devices that start behaving consistently all together. As you can understand, if 10 sailing autopilots were listening to the same spoofed signal and we start rotating the frame of reference then all of them will be taking consistent decisions at the same time. The above algorithm more or less remains the same but this time you want to cluster devices whose bearing (derived bearing) deviated by a consistent value at the same time. That is, they all appear to be adjusting at the same time and by the same amount. (As you can see here, no reason to assess the similarity of specific signals, we work with location directly).
    • If you are trying to understand if a single device's GPS is being spoofed, then that is even more challenging and there you would need to have access to other data as well (again to try to confirm the story the GPS is telling you).

Hope this helps


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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