You definitely can apply Fourier Theorem to strides convolutions. I actually did that in my GitHub repo, if you want to check it out: https://www.github.com/fkodom/fft-conv-pytorch/tree/master/fft_conv.py

Unfortunately, you don’t get any additional performance increases by using striding. With direct convolutions, you can just skip over the values you don’t need. But with Fourier Convolutions, you just have to compute the full output, and throw away the parts you don’t need at the end.