Convolution diagonalises in the Fourier basis

ProofIntermediate⏱ 30 minDeep Learningfourierconvolution theoremdiagonalisation

Theory: Convolution, Recurrence and Normalisation →

Problem

Prove $\widehat{k*x} = \hat k\cdot\hat x$ for the discrete Fourier transform on $\Z_n$ , and show that the characters $\chi_\omega[i] = e^{2\pi i\omega i/n}$ are eigenvectors of every convolution operator. State two practical consequences.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Receptive field growth with depth and dilation	Deep Learning	Numerical	Beginner	15 min
The RNN gradient is a repeated matrix product	Deep Learning	Proof	Intermediate	30 min
Translation-equivariant linear maps are convolutions	Deep Learning	Proof	Intermediate	30 min
Normalisation makes weights scale-invariant	Deep Learning	Proof	Advanced	30 min
The LSTM cell-state Jacobian	Deep Learning	Proof	Advanced	30 min