You could probably convert the convolution into a single linear transformation of the image and use something like a randomized sketching algorithm to approximate the transform (https://arxiv.org/pdf/1609.00048.pdf)