Szybka średnia funkcja różnicy kwadratowej

Question

Zastanawiam się, czy ktokolwiek wie o szybkiej (tj. O (N log (N))) obliczaniu funkcji średniej kwadratowej różnicy (ASDF) lub funkcji średniej różnicy wielkości (AMDF) dla okresowy sygnał, lub jest to nawet możliwe.

Wiem, że można użyć FFT do obliczenia okresowej korelacji krzyżowej. Na przykład, w kodzie Matlab,

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

jest równoznaczne z dużo szybciej

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

Czy istnieje podobna "szybko" algorytm

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

lub

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

?

Answer 1

można poszerzyć swoją definicję asdf następująco:

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

który upraszcza do

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