# [PYTHON MATRIX-SIG] autocorrelation functions?

**David Ascher
**
da@maigret.cog.brown.edu

*Mon, 14 Oct 1996 10:15:47 -0400 (EDT)*

>* > 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
=================