# [SciPy-User] fast autocorrelation Classic List Threaded 5 messages Open this post in threaded view
|

## [SciPy-User] fast autocorrelation

 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))) _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|

## Re: fast autocorrelation

 scipy.fftpack has two functions for that: rfft and irfft. They are both faster than fft/ifft, so maybe you want to use that? Or is it still too slow? -- Dr. Barbier de Reuille, PierreInstitute of Plant SciencesAltenbergrain 21, CH-3013 Bern, Switzerlandhttp://www.botany.unibe.ch/associated/systemsx/index.php On 27 February 2013 15:02, Neal Becker wrote: 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))) _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|

## Re: fast autocorrelation

 Pierre Barbier de Reuille wrote: > scipy.fftpack has two functions for that: rfft and irfft. They are both > faster than fft/ifft, so maybe you want to use that? Or is it still too > slow? > I believe irfft will do complex->real (just as rfft does real->complex). In this case, we have frequency domain values, but they are pure real.  So we want ifft from real->complex. _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user