[PYTHON MATRIX-SIG] autocorrelation functions?

[David Ascher]

> > Isn't the O(n^2) operation of autocorrelation mathematically
> > equivalent to the O(n ln n) auto-convolution operation?
> > 
> >     ac(x)=inverse_fft(fft(x)^2)
> 
> Almost. The difference between convolution and correlation is
> a conjugation: 
>   xfft = fft(x)
>   inverse_fft(xfft*conjugate(xfft))
> (untested, as always).

Great, this is perfect.  Two more questions

1) I can do 2d fft's and 2d inverse fft's -- what kind of
   autocorrelation metric would that use (meaning if autocorrelation is
   the function relating distance between elements and their
   correlation, what distance metric does it use)?

2) I'd really appreciate a reference on these sorts of tidbits --
   computational algorithms which cross standard boundary distinctions.
   Can anyone recommend such a book?

Thanks.

--david

=================
MATRIX-SIG  - SIG on Matrix Math for Python

send messages to: matrix-sig@python.org
administrivia to: matrix-sig-request@python.org
=================