[Numpy-discussion] reformulating a series of correlations as one fft, ifft pair

[Stéfan van der Walt]

Hi Paul

On 19 April 2010 08:36, Paul Northug <pnorthug at gmail.com> wrote:
> I am having trouble reformulating a series of correlations as a single
> fft, ifft pair.
>
> I have a set of kernels phi : (M = channel, N = kernel, T = time)
> correlated with signal a : (N, P+T-1) yielding x : (M, T).
>
> The correlation, for now, is only in the last dimension, with the two
> other dimensions degenerate. Below are 4 implementations (x == y == z
> != w). I would like to reformulate the operation as a single pair of
> 3d ffts to compare how it fares for different problem dimensions but I
> am not able to do it. Implementation #4 is incorrect. Please note the
> .conj() to get correlations rather than convolutions.
>
> Any tips would be appreciated. Optimally, I would not have to pad with
> too many zeros as the matrices can be quite large. The challenge is to
> beat implementation 2 as P grows. M, N, P are typically on the order
> of 10^2 and T, 10^3.

I haven't checked your code in detail, but I'll mention two common
problems with this approach in case it fits:

1) When convolving a KxL with an MxN array, they both need to be zero
padded to (K+M-1)x(L+N-1).
2) One of the signals needs to be reversed and conjugated.

Also have a look at scipy.signal.fftconvolve.  For real 2D images, I use:

def fft_corr(A, B, *args, **kwargs):
    return ss.fftconvolve(A, B[::-1, ::-1, ...], *args, **kwargs)

Regards
Stéfan