# “Circular shift - invariant” distance

Couldn't decide whether the question belongs on Mathematics or here, but I guess I'll ask it here.

I've got a discrete - valued function defined on a finite segment of a line that looks like this:

Then the task is, given a set of other functions, find a function in this set that is the closest - in some way that I'm about to describe - to the original one.

The problem is that the candidate functions may be, actually, circularily shifted with respect to one another. If the functions were not shifted, any reasonable norm of difference (l1, l2, any lp, I guess) would've been okay. I also want to notice that I do not necessarily want a function that satisfies the mathematical definition of a norm (or even a distance) - I just want the problem solved.

The obvious thing to do is to look at the maximum of circular cross - correlation. However, this is actually a bad idea because even if I normalize both compared function by their max values, the function f(x) = 1 will give the maximal value with any other function.

I want to know whether there is some standard approach for such a situation or should I just compute an l1 - norm for every possible circular shift and then take the minimum value.

• You say that the functions in the set can be shifted versions of one another. Can they also be shifted versions of the original? – MBaz Feb 9 '15 at 15:15
• Why do you say that the cross-correlation of any function with $f(x)=1$ is maximal? Have you tried to verify that? – MBaz Feb 9 '15 at 15:18
• The magnitude of DFT is shift invariant, perhaps this could help. – ThP Feb 9 '15 at 19:53
• @MBaz Sorry for the inaccuracy about f(x) = 1. I should probably add that this would be true if we would deal only with non - negative functions. If so, the function that is equal to its max value everywhere will deliver the maximum. This, however, illustrates the fact that cross - correlation does not actually reflect the distance between the functions - even if functions are not similar, larger magnitudes will contribute. – Vossler Feb 10 '15 at 7:30
• @MBaz An idea - maybe I should normalize both functions not by the maximum, but by the l1 norm? As for your first questions, the answer is yes, that is exactly what I meant. They do not have to be shifted versions of one another, they MAY be shifted versions of the original = and the task is to find such a function. – Vossler Feb 10 '15 at 7:32