[SciPy-User] fast autocorrelation

Neal Becker ndbecker2@gmail....
Wed Feb 27 08:02:44 CST 2013


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)))



More information about the SciPy-User mailing list