Discrete Fourier analysis

Fourier analysis on finite abelian groups and the Boolean cube: DFT and FFT, Plancherel, finite uncertainty, Young and Hausdorff–Young, Riesz–Thorin on finite sets, influences and noise operators.

• Fourier analysis on the Boolean cube
• Fourier transform on finite abelian groups
• Donoho–Stark uncertainty principle
• Influences and the noise operator on the Boolean cube
• Riesz–Thorin interpolation theorem
• Hausdorff–Young inequality on finite abelian groups
• Young's convolution inequality on finite groups

TheoremConvolution theorem for the discrete Fourier transform#✓fully proved

Let \(n \ge 1\). For \(\varphi : \mathbb{Z}/n\mathbb{Z} \to \mathbb{C}\) write \(\hat\varphi(k) = \sum_{j \in \mathbb{Z}/n\mathbb{Z}} e^{-2\pi i jk/n} \varphi(j)\) for its discrete Fourier transform, and let \(\mathcal{F}^{-1}\) be the inverse of the map \(\varphi \mapsto \hat\varphi\). Then for all \(f, g : \mathbb{Z}/n\mathbb{Z} \to \mathbb{C}\) and every \(t \in \mathbb{Z}/n\mathbb{Z}\), the value at \(t\) of \(\mathcal{F}^{-1}\) applied to \(k \mapsto \hat f(k)\,\hat g(k)\) equals the circular convolution \(\sum_{j \in \mathbb{Z}/n\mathbb{Z}} f(j)\,g(t - j)\).

theorem invDFT_mul_dft (f g : ZMod n → ℂ) (t : ZMod n) :
    dft.symm (fun k => dft f k * dft g k) t = ∑ j : ZMod n, f j * g (t - j)

Sources

• MIT 6.046J Spring 2015 Lecture 3, polynomial product theorem, cyclic form.

Used by 3

Used byZero-padded circular autocorrelation equals linear autocorrelation · FFT circular convolution with root \(e^{-2\pi i/n}\) computes the cyclic convolution · FFT circular convolution with root \(e^{2\pi i/n}\) computes the cyclic convolution

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.