Discrete Fourier transform

We consider the discrete counterpart of the relation discussed in the previous part:

\[F_k = \frac{1}{L} \int_{0}^{L} f \left( x \right) \twiddle{- 2 \pi}{k x}{L} dx.\]

In particular, we describe the continuous function \(f \left( x \right)\) as the superposition of \(N\) Dirac delta functions having non-zero value at \(x_n \in \left[ 0, L \right)\), yielding

\[ \begin{align}\begin{aligned}F_k & \approx \frac{1}{L} \int_{0}^{L} \sum_{n = 0}^{N - 1} f_n \delta \left( x - x_n \right) \twiddle{- 2 \pi}{k x}{L} dx\\& = \sum_{n = 0}^{N - 1} f_n \twiddle{- 2 \pi}{k x_n}{L}.\end{aligned}\end{align} \]

It should be noted that, the integral and the summation are interchanged, which needs careful consideration but is accepted anyway here.

Although the sampling points \(x_n\) can be arbitrary chosen, we let them

\[x_n = n \frac{ L }{ N },\]

leading to

\[F_k = \sum_{n = 0}^{N - 1} f_n \twiddle{- 2 \pi}{k n}{N}.\]

Correspondingly, we notice

\[ \begin{align}\begin{aligned}\frac{1}{N} \sum_{k = 0}^{N - 1} F_k \twiddle{2 \pi}{k n}{N} & = \sum_{k = 0}^{N - 1} \left\{ \sum_{m = 0}^{N - 1} f_m \twiddle{- 2 \pi}{k m}{N} \right\} \twiddle{2 \pi}{k n}{N}\\& = \frac{1}{N} \sum_{m = 0}^{N - 1} \left\{ f_m \sum_{k = 0}^{N - 1} \twiddle{2 \pi}{k \left( n - m \right)}{N} \right\}\\& = \frac{1}{N} \sum_{m = 0}^{N - 1} f_m N \delta_{nm}\\& = f_n,\end{aligned}\end{align} \]

where we use an identity with \(n \in \mathbb{Z}\):

\[\sum_{k = 0}^{N - 1} \twiddle{2 \pi}{k n}{N} = N \delta_{n0}.\]

Derivation

For \(n = 0\) (or in general \(n = N m\) with \(m \in \mathbb{Z}\)), it is obvious that

\[\sum_{k = 0}^{N - 1} 1 = N.\]

Otherwise, we have

\[\sum_{k = 0}^{N - 1} \twiddle{2 \pi}{n k}{N} = \frac{ 1 - \exp \left( 2 \pi n I \right) }{ 1 - \twiddle{2 \pi}{n}{N} } = 0,\]

where we adopt the formula to calculate the sum of geometric progression.

In summary, the discrete Fourier transform and its inverse transform are given by:

\[ \begin{align}\begin{aligned}F_k & \equiv \sum_{n = 0}^{N - 1} f_n \twiddle{- 2 \pi}{k n}{N} \equiv \dft{k}{N}{f_0}{f_1}{f_{N - 1}},\\f_n & \equiv \frac{1}{N} \sum_{k = 0}^{N - 1} F_k \twiddle{2 \pi}{k n}{N} \equiv \idft{n}{N}{F_0}{F_1}{F_{N - 1}},\end{aligned}\end{align} \]

where \(\seq{k}{0}{1}{N - 1}\) and \(\seq{n}{0}{1}{N - 1}\), respectively. Note that both transforms are linear operators yielding linear maps: \(\mathbb{C}^N \rightarrow \mathbb{C}^N\).