Let's say I have two vectors A and B, of lengths, m, and n respectively. They are not "signals" but a collection of ordered time marks or indexes from another two "original" longer vectors (let's call them X and Y).
I try to compare A and B to "estimate" the similarity between X and Y. If they are aligned I can use a simple Jaccard index to do it. However, X and Y (and so A and B) can be delayed and/or steched with each other. I've assumed that if X and Y are similar, then B should be a linear function of A (B = c*A+d, c and d scalars). Besides, some elements could not match exactly or be missing in the other vector because A and B are of different lengths. For instance:
A = [1 6 12 25 36 37 40], B = [3 13 25 73 82]
Should match the following pairs:
C = [[1,3],[6,13],[12,25],[36,73],[40,82]] -> B = 2*A+1
What algorithm or method can I use to find the gain c and offset d to get the best alignment between A and B? In other words, the parameters that maximize the amount of common elements between both these vectors.
Typically A,B are around 150 elements, and 0.8 < c < 1.2.

A little context: I'm trying to make a song dedupe application in C#. In fact, X and Y are audio firngerprints (chromaprints) made with AcousticID, which are basically binary matrixes (every row is a 32-bit integer). This questions could be directly solved to align X and Y but I think it could be harder due to the "noisy" nature of the prints (sample) and the larger size of vectors.


migrated from stackoverflow.com Jul 31 '18 at 1:40

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ This might help. Although it does not already include stretching. But this is something you should be able to incorporate. $\endgroup$ – Nico Schertler Jul 28 '18 at 5:34
  • $\begingroup$ See dsp.stackexchange.com/questions/736/… $\endgroup$ – geometrikal Sep 29 '18 at 7:46

The most similar method to your thought is finding a "linear regression". Hence, you can use a c# library or code to compute "linear regression" for the points of in A|B elements pairs.

  • $\begingroup$ Yes, that was my first idea, but the usual method I know (Linear Least Squares) require the vectors to be the same length. Is there another method? $\endgroup$ – adrianjgp Jul 28 '18 at 16:32

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.