The convolution theorem says that a 2-d cyclic convolution like $C = U \ast V$ can be evaluated more quickly than doing the raw sum $C_{i,j} = \sum_{a,b}^n U_{a,b} V_{i-a,j-b}$ for each point (assume indices wrap around mod $n$). Instead, you do a point-wise product in fourier-space like $C = \mathfrak{F}^{-1} (\mathfrak{F} U \cdot \mathfrak{F} V)$ and this takes quadratic time with polylog overhead instead of quartic time.
I have an expression that's very similar to a convolution, but there's an extra twiddle factor. Here is the expression:
$$D_{i,j} = \sum_{a,b}^n \omega^{ab} U_{i-a,b} V_{a,j-b}$$
Where $\omega = e^{2 \pi \sqrt{-1} / n}$ and $n$ is the width and height of the 2-d arrays. As you can see, this is a cyclic convolution (assume that indices wrap around mod $n$) except that one of the coordinates has been reversed and also there's an extra root-of-unity twiddle term.
Is it still possible to compute $D$ quickly in Fourier space given $U$ and $V$, by tweaking the convolution theorem, or is the twiddle term a significant obstacle?