[SciPy-User] fast autocorrelation

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[SciPy-User] fast autocorrelation

Neal Becker
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
Reply | Threaded
Open this post in threaded view
|

Re: fast autocorrelation

Pierre Barbier de Reuille
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
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
Reply | Threaded
Open this post in threaded view
|

Re: fast autocorrelation

Neal Becker
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
Reply | Threaded
Open this post in threaded view
|

Re: fast autocorrelation

Pierre Barbier de Reuille
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:
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


_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: fast autocorrelation

Fabrice Silva-2
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