# Fourier transform diagonalizes time-invariant convolution operators

I got the following paragraph from the book "A wavelet tour of signal processing" chapter one, page 2.

The Fourier transform is everywhere in physics and mathematics because it diagonalizes time-invariant convolution operators. It rules over linear time-invariant signal processing, the building blocks of which are frequency filtering operators.

How is it (illustrated) formulated mathematically?

• Hi! This is a bit broad. What specifically are you looking for? A mathematical definition of the Fourier transform is really in every thinkable textbook on signals and systems, about solid state physics, and on a thousand places, including the wikipedia, on the internet. So, I presume this isn't about that. But what is it about, then? I know you're a mathematician, so could you please put this like a mathematician? – Marcus Müller Nov 5 '20 at 15:40
• This question essentially requires a quite long answer, but then which would turn it into a wiki-tale rather than an se-pill. If instead a short answer is provided, however, it will hardly make any sense to anyone who already didn't know the long answer... – Fat32 Nov 5 '20 at 17:04

For linear time invariant systems, complex exponentials are eigenfunctions - see here and here. The complex exponentials are the basis functions used in the Fourier transform i.e. the FT is a linear combination of complex exponentials.

The following is a slightly modified version of here: The convolution operator acting on $$f(y)$$ is given by:

$$g(y)=\int_{-\infty}^{\infty}f(y-x)h(x)dx$$ Applying the convolution operator to $$f(y)=e^{iky}$$ gives $$\begin{eqnarray*} g(y)&=&\int_{-\infty}^{\infty}e^{ik(y-x)}h(x)dx \\ g(y)&=&e^{iky}\int_{-\infty}^{\infty}e^{-ikx}h(x)dx \\ g(y)&=&f(y)\lambda, \end{eqnarray*}$$

where $$\lambda = H(k)=\int_{-\infty}^{\infty}e^{-ikx}h(x)dx$$ is the Fourier transform of $$h(x)$$.

To see the diagonalization effect of the eigenvectors, we have by definition: $$Ax_n=\lambda_n x_n,$$. Thus the complete set of eigenvectors/eigenvalues can be written as: $$AX=\Lambda X,$$ where $$\Lambda =diag(\lambda_1 ... \lambda_N)$$ and each column of $$X$$ is the corresponding eigenvector. Finally, because the eigenvectors are orthogonal $$X^T = X^{-1}$$ so we have: $$X^TAX=\Lambda.$$

• I got the point. Thanks for your attention. – Ali Bagheri Nov 6 '20 at 16:30
• Complex exponentials are eigenfunctions for sure. Maybe not "the eigenfunctions" – Laurent Duval Nov 6 '20 at 23:17
• @LaurentDuval Yes - I made the edit to reflect that. Thanks. – David Nov 7 '20 at 13:35

TL;DR: Fourier is the logarithm of the convolution.

Doing a convolution (linear time-invariant operator) is a quite involved processing in the original (primal) domain: it involves intricate sums and products of an operator $$h$$ and signals $$s$$ at different indices:

$$\sum_k h[k]\times x[n-k]\,.$$

With a Fourier transform, you transform the whole information for the operator $$h$$ and data $$x$$ in the primal domain onto a novel dual (frequency) domain, in $$\hat{h}$$ and $$\hat{x}$$. Then the result of convolution becomes:

$$\hat{h}[m] \times \hat{x}[m]$$

which is a simple index-by-index product. Hence the term "diagonalization": from products of two indices, $$[k]$$ and $$[n-k]$$, Fourier turns them into a product of a single index $$[m]$$ times $$[m]$$.

To make the above a bit simpler, Fourier is to convolution what logarithms are to multiplication. Let us forget the carry for a moment. Doing a multiplication is complicated, especially for large numbers: one has to multiply thousands to tens and add them to products of hundreds. Logarithms turn multiplication into adds: you (almost) have to add figures in the same position (lest the carry), instead of combining figures in different powers.

For ages, people have used logarithm tables or logarithmic sliding rulers as analog computers. Logarithmic tables and rulers have been very important in days before computers, to allow computations in engineering, astronomy, etc.

Fourier principles, tools and fast librairies are the nowadays analogs of logarithms, that helped shaped our digital world. The FFT algorithm is often considered one of the most important algorithms. Indeed, there exists FFT based multiplication of large numbers.