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.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, Pierre Institute of Plant Sciences Altenbergrain 21, CH-3013 Bern, Switzerland http://www.botany.unibe.ch/associated/systemsx/index.php On 27 February 2013 15:02, Neal Becker <[hidden email]> wrote: I'm trying to use fft to do fast auto-correlation. (Actually, my real problem _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
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 |
My bad, I hadn't read the description fully. -- Dr. Barbier de Reuille, Pierre Institute of Plant Sciences Altenbergrain 21, CH-3013 Bern, Switzerland http://www.botany.unibe.ch/associated/systemsx/index.php On 27 February 2013 15:48, Neal Becker <[hidden email]> wrote:
_______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
In reply to this post by Neal Becker
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() _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
Free forum by Nabble | Edit this page |