I have two discrete signals, $A$ and $B$ (both with $L$ values). I want to look for the section (of a certain length $R$) on each signal ($[A_1:A_1+R]$ and $[B_1:B_1+R]$) where they are the most similar (using some similarity metric, say Manhattan distance) (technically, I just need to know how similar the most similar sections of the two signals). Right now, I have a double loop that compares each section of signal $A$ to each section of signal $B$, and choose the $A_1$ and $B_1$ that lead to the most similar sections. However, that gets really slow as I scale up. Is there some other, more efficient way of doing this?

  • $\begingroup$ The straightforward solution complexity is O(L^3), there exist O(L^2) algorithms. The ideas of the stackoverflow.com/questions/13006556/… question may be useful. Especially inspiring (as concerns the signal matching) are hints from the answer anchored in ref, citing from the answer "... You can modify this algorithm to do more fancy searches like ignoring case, fuzzy matching the substring, look for multiple substrings etc. ...". Check also bioinformatics' BLAST algorithm. $\endgroup$
    – V.V.T
    Aug 4 '20 at 3:21
  • $\begingroup$ @V.V.T But isn't that not doing much better than I already have? $\endgroup$
    – DUO Labs
    Aug 4 '20 at 3:59
  • $\begingroup$ Find algorithmic complexity of your "double loop" solution and compare it with O(L^2) $\endgroup$
    – V.V.T
    Aug 4 '20 at 4:26
  • $\begingroup$ @V.V.T If I did it correctly, shouldn't my solution be $O(R*L^2)$? $\endgroup$
    – DUO Labs
    Aug 4 '20 at 13:46
  • $\begingroup$ Just noticed the fragment length is known beforehand ("a certain length R"). You can aspire to O(L*R): iq.opengenus.org/longest-common-substring . Join the BLAST and Dynamic Programming approaches $\endgroup$
    – V.V.T
    Aug 5 '20 at 0:26

The best way to achieve this, to my knowledge, is a matched filter or cross-correlation. This will tell you not only how well $A$ and $B$ match but will also give you a time offset for it. Just make sure to normalized based on the energy of both signals so you aren't getting false positives if that's a major concern.

If you're looking for a more strict time match (the signal similarity needs to be in-time) then you only want to look at $R[0]$ where $R[n] = A[n] \star B[n]$.

Technically, cross-correlation of non Wide Sense Stationary signals is two-dimensional. So if you're interested in the particular time when the signals best match up with no offset, your process may look something like this over $Z$ trials.

$$ \begin{align} R[n,m] &= E\{A[n]B^*[m]\}\\ m &= n\\ R[n] &= E\{A[n]B^*[n]\}\\ R[n] &= \frac{1}{Z}\sum_{\zeta=0}^{Z-1}{A_\zeta[n]B_\zeta[n]} \end{align} $$

If you clarify what sort of signals these are and what about their matching is important, I think it would help narrow down what solution would best fit.

  • $\begingroup$ I've looked into cross-correlation, but it didn't fit my need because it only has one signal's offset as a variable, instead of both like I want. $\endgroup$
    – DUO Labs
    Aug 4 '20 at 13:49
  • $\begingroup$ @DUO I’m afraid that’s not quite correct. Cross-correlation, when there is an assumption of wide sense stationarity, can be expressed as a function of the single value ‘n’ which is the offset between signal one and signal two. Cross-correlation can also be expressed as a function of two dimensions: the time index of A and the time index of B, or the time index of A and the offset of B from A (the former is more common). This 2D version of cross-correlation is probably what you want. $\endgroup$
    – Keegs
    Aug 4 '20 at 15:19
  • $\begingroup$ So I'm guessing that there's a version of cross-correlation that offsets both A and B by different numbers and calculates the similarity between the signals by starting from those offsets? Or am I misunderstanding something? $\endgroup$
    – DUO Labs
    Aug 4 '20 at 15:28
  • $\begingroup$ @DUO It doesn’t so much offset A and B as it indexes into A and B at times n and m. This requires you to ideally get multiple trials for A and B otherwise your statistical basis for saying the processes are correlated is weak. Check out the lower left subplots here for a graphical example. colab.research.google.com/drive/… $\endgroup$
    – Keegs
    Aug 4 '20 at 16:16
  • $\begingroup$ Ok, thanks. I'll check it out. $\endgroup$
    – DUO Labs
    Aug 4 '20 at 17:21

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.