Fast Average Square Difference Function

Question

I'm wondering if anyone knows of a fast (i.e. O(N log(N)) ) method of calculating the average square difference function (ASDF) or average magnitude difference function (AMDF) for a periodic signal, or it is even possible.

I know that one can use the FFT to calculate the periodic cross correlation. For example, in Matlab code,

for i=1:N
xc(i)=sum(x1*circshift(x2,i-1));
end

is equivalent to the much faster

xc=ifft(fft(x1).*conj(fft(x2));

Is there a similar "fast" algorithm for

for i=1:N
ASDF(i)=sum((x1-circshift(x2,i-1)).^2)/N;
end

or

for i=1:N
AMDF(i)=sum(abs(x1-circshift(x2,i-1)))/N;
end

?

Answer 1

This might be worth looking at:

http://windale.com/transformnet.php

It's not free (or cheap), but if you have a serious need, they do offer source code (and a 30 day guarantee).

Answer 2

You can expand your definition of ASDF as follows:

for i = 1:N
    asdf(i) = (sum(x1.^2) - 2*sum(x1*circshift(x2,i-1)) + sum(x2.^2))/N;
end

which simplifies to

asdf = (-2*ifft(fft(x1).*conj(fft(x2))) + sum(x1.^2) + sum(x2.^2))/N;