Do there exist mathematical transforms other than the Fourier Transform for which there exists some sort of a fast convolution theorem?

Question

One nice property of the Fourier transform is it's famous convolution theorem :

$$f*g = \mathcal{F}^{-1} \left\{ \mathcal{F}\left\{ f \right\} \cdot \mathcal{F}\left\{g\right\} \right\}$$

If we want to compute the (circular) convolution between two functions we can instead Fourier transform them separately, multiply their Fourier coefficients with each other and then inverse transform them.

Now to my question : do there exist any other mathematical transform (in specific integral transforms are of interest, but other "things" or concepts I am not yet aware of may be of interest as well) which have the same or similar useful properties if the goal is the simplifying the calculation of a convolution?

Answer 1

Yes, for the Mellin convolution

$$[f(x) * g(x)](y)=\int\limits_0^\infty f(x)\, g\left(\frac{y}{x}\right)\,\frac{dx}{x}\tag{1}$$

one has

$$\mathcal{M}_y[[f(x) * g(x)](y)](s)=\mathcal{M}_x[f(x)](s)\cdot \mathcal{M}_x[g(x)](s)\tag{2}$$

where

$$\mathcal{M}_x[f(x)](s)=\int\limits_0^\infty f(x)\, x^{\,s-1}\, dx\tag{3}$$

is the Mellin transform.

---

Note the identity for the commutative Mellin convolution defined in formula (1) above is $\delta(x-1)$ whereas the identity for Fourier convolution which is also commutative is $\delta(x)$.

---

For the alternate Mellin convolution

$$[f(x) * g(x)](y)=\int\limits_0^\infty f(x)\, g\left(y x\right)\, dx\tag{4}$$

one has

$$\mathcal{M}_y[[f(x) * g(x)](y)](s)=\mathcal{M}_x[f(x)](1-s)\cdot \mathcal{M}_x[g(x)](s)\tag{5}$$

but this alternate Mellin convolution is not commutative. For example

$$[\delta(x-1) * g(x)](y)=\int\limits_0^{\infty} \delta(x-1)\, g(x y) \, dx=g(y)\tag{6}$$

whereas

$$[g(x) * \delta(x-1)](y)=\int\limits_0^{\infty} g(x)\, \delta(x y-1) \, dx=\frac{g\left(\frac{1}{y}\right)}{y}\tag{7}.$$

Answer 2

The discrete Fourier transform, say in the form of the evaluation/interpolation ring isomorphism $$ \mathbb{C}[x]/(x^n-1)\cong\prod_i\mathbb{C}[x]/(x-\zeta^i)\cong\mathbb{C}^n $$ takes cyclic convolution to pointwise multiplication. Doing this quickly goes under the name of the fast Fourier transform (FFT) (e.g. decimation in time/frequency).

Replacing $\mathbb{C}$ with a finite field with the appropriate roots of unity gives the so-called NTT (number theoretic transform) which is used in lattice-based post-quantum cryptography to speed up multiplication (e.g. Kyber, Dilithium, and Falcon).

The Hadamard transform also get some use, $$ \hat{f}(x)=\sum_uf(u)(-1)^{\langle x,u\rangle}, \quad f\in (\mathbb{Z}/2\mathbb{Z})^n, \ \hat{f}\in\{\pm1\}^n. $$