[SciPy-User] fast autocorrelation
Fabrice Silva
silva at lma.cnrs-mrs.fr
Wed Feb 27 10:14:08 EST 2013
Le mercredi 27 février 2013 à 09:02 -0500, Neal Becker a écrit :
> I'm trying to use fft to do fast auto-correlation. (Actually, my real problem
> is slightly different, but I'll leave that detail out).
>
> The input sequence is complex, so a complex->complex FFT is used. A length 2N
> FFT is used with 0-padding to perform linear correlation.
>
> If now in FFT output we take magnitude-squared, we have a real sequence. A
> complex IFFT could be used to get the autocorrelation output, but that would be
> wasteful.
>
> My question is, is there a trick to more efficiently compute IFFT where the
> input is real?
>
> A couple of thoughts:
> 1. there is a nice trick for real->complex fft (not ifft)
> 2. an fft can be used to compute ifft as ifft (x) = conj (fft (conj (x)))
For #1:
np.fft.rfft
For #2:
regarding your real PSD (after squaring the output of FFT), the inner
conj is trivial, and the normalization by the length of the sequence is
lacking:
if x real, ifft(x) = 1/n * conj(fft(x))
so may use for your purpose (just compute positive lag samples) :
1/n * np.fft.rfft(PSD).conj()
More information about the SciPy-User
mailing list