title: Fast Average Square Difference Function
body: <p>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.</p>
  
  <p>I know that one can use the FFT to calculate the periodic cross correlation. For example, in Matlab code,</p>
  
  <pre><code>for i=1:N
  xc(i)=sum(x1*circshift(x2,i-1));
  end
  </code></pre>
  
  <p>is equivalent to the much faster</p>
  
  <pre><code>xc=ifft(fft(x1).*conj(fft(x2));
  </code></pre>
  
  <p>Is there a similar "fast" algorithm for</p>
  
  <pre><code>for i=1:N
  ASDF(i)=sum((x1-circshift(x2,i-1)).^2)/N;
  end
  </code></pre>
  
  <p>or</p>
  
  <pre><code>for i=1:N
  AMDF(i)=sum(abs(x1-circshift(x2,i-1)))/N;
  end
  </code></pre>
  
  <p>?</p>