📂Fourier Analysis

Discrete Fourier Inversion

Formula¹

Let’s denote the Discrete Fourier Transform of $\mathbf{a} = (a_{0}, a_{1}, \dots, a_{N-1}) \in \mathbb{C}^{N}$ as $\hat{\mathbf{a}} = (\hat{a}_{0}, \hat{a}_{1}, \dots, \hat{a}_{N-1}) \in \mathbb{C}^{N}$.

$$\mathcal{F}_{N}(\mathbf{a}) = \hat{\mathbf{a}},\quad \hat{a}_{m}=\sum_{n=0}^{N-1}e^{-i2\pi mn /N}a_{n}$$

Then, the following holds.

$$a_{n} = \dfrac{1}{N} \sum \limits_{m=0}^{N-1} e^{i 2 \pi m n / N} \hat{a}_{m}$$

Explanation

This is known as the inverse formula for discrete Fourier transform.

Proof

Lemma

For $m = 0, 1, \dots, N-1$, let’s set it as follows.

$$\mathbf{e}_{m} = \left( 1, e^{i 2\pi m/N}, e^{i 2\pi 2m/N}, \dots, e^{i 2\pi (N-1)m/N} \right)$$

Then, $\left\{ \mathbf{e}_{m} \right\}_{m=0}^{N-1}$ is a basis of $\mathbb{C}^{N}$, and $\left\| \mathbf{e}_{m} \right\|^{2} = N$ holds.

Following the lemma, for any $\mathbf{a} \in \mathbb{C}^{N}$ the following is true.

$$\mathbf{a} = \dfrac{1}{N} \sum _{m=0}^{N-1} \left\langle \mathbf{a}, \mathbf{e}_{m} \right\rangle \mathbf{e}_{m}$$

Calculating the inner product $\left\langle \mathbf{a}, \mathbf{e}_{m} \right\rangle$, by the definition of the discrete Fourier transform, it follows that.

$$\left\langle \mathbf{a}, \mathbf{e}_{m} \right\rangle = \sum _{n=0}^{N-1} a_{n}e^{i 2\pi nm/ N} = \hat{a}_{m}$$

Substituting this into the above equation yields the following.

$$\mathbf{a} = \dfrac{1}{N} \sum _{m=0}^{N-1} \hat{a}_{m} \mathbf{e}_{m}$$

$$a_{n} = \dfrac{1}{N} \sum _{m=0}^{N-1} e^{i 2\pi m n / N} \hat{a}_{m}$$

■