# Fast calculations using fast-Fourier convolution

Consider an array $$X$$ with shape $$H \times W$$. Let $$Y$$ be the other array of the same shape and $$Z$$ is an array of shape $$h \times w$$.

We want to construct an array $$R$$ of shape $$(H-h + 1, W-w+ 1)$$ by the following rule:

$$\displaystyle R[k, l] = \sum_{i, j} (X[i,j] - Y[i,j])^2 +$$ $$\sum_{i=0}^{h-1}\sum_{j=0}^{w-1}[(X[k + i, l + j] - Z[i, j])^2 - (X[k + i, l + j] - Y[k + i, l + j])^2]$$

So it's better to represent it via the image: we erase some subarray of size $$h \times w$$ in $$X - Y$$, change it by $$X_{h, w} - Z$$ and compute the sum of squares.

Using dynamic programming we can solve it pretty fast, but it's still a time-consuming process. I think that it's possible to calculate such an array using fast Fourier convolutions. But we need to determine convolution arrays to do that.

Any hints?