Cross correlation of medium sized arrays

Question

I have 16 1D arrays with approximately 10-11 million double-precision elements each. I need to execute a cross-correlation across them, i.e., 1 with 2, 1 with 3, ..., 1 with 16, 2 with 3, 2 with 4, ..., 2 with 16, and so on. This cannot be done efficiently on my MacBook Intel Core 2 duo 2.4 GHz, with 4GB of RAM. My question is, what is the typical approach, if not brute force (faster processor, more RAM) that people use to overcome this problem, or problems like it? Thanks!

Answer 1

If you calculate the Fourier transform of each of your arrays, you should be able to use the transformed arrays to efficiently calculate the cross-correlation between each pair of the original input arrays. See the "Properties" section of the Wikipedia article I linked to for the identity to use.

Answer 2

The cross-correlation function in numpy is ridiculously slow. The openCV library has a numpy friendly cross-correlation function available. Even if you try to implement a frequency domain aproach, you won't beat the openCV library, as there are more tricks available to speed up a cross-correlation calculation. I posted about this before:

Computing cross-correlation function?

I believe the code is based on the tricks detailed in the following paper:

J. P. Lewis, “Fast template matching,” in Vision Interface, 1995, vol. 95, pp. 120–123.