James A. Brofos quantitative strategies researcher

The Fourier Transform (II)

Let $\mu : \mathfrak{B}(\mathbb{R}) \to \mathbb{C}$ be a complex Borel measure. We define the Fourier transform of $\mu$ by the equation, \begin{align} \hat{\mu}(\xi) = \int_{-\infty}^{\infty} \exp(-2\pi i x\xi) ~\mu(\mathrm{d}x). \end{align}
In the case where $\mu(\mathrm{d}x) = f(x) ~\mathrm{d}x$ for some integrable $f : \mathbb{R}\to \mathbb{C}$ we have that the Fourier transform of the measure is equivalent to the Fourier transform of the function $f$. This is seens as follows: \begin{align} \hat{\mu}(\xi) &= \int_{-\infty}^{\infty} \exp(-2\pi i x\xi) ~\mu(\mathrm{d}x) \\ &= \int_{-\infty}^{\infty} f(x) \exp(-2\pi i x\xi) ~\mathrm{d}x \\ &= \hat{f}(\xi). \end{align}

Consider the case of the Dirac delta measure. The Fourier transform is \begin{align} \hat{\delta}(\xi) &= \int_{-\infty}^\infty \exp(-2\pi ix\xi) ~\delta(\mathrm{d}x) \\ &= \exp(-2\pi i \xi 0) \\ &= 1. \end{align}

We are now in a position to motivate the discrete Fourier transform as the Fourier transform of a particular complex Borel measure. Consider the measure \begin{align} \mu(\mathrm{d}x) = \sum_{n=0}^{N-1} \delta_{n/N}(\mathrm{d}x) \end{align} where $\delta_{k} : \mathfrak{B}(\mathbb{R}) \to \{0, 1\}$ is the Dirac measure located at $k\in\mathbb{R}$. Now let $f : \mathbb{R}\to\mathbb{C}$ be a function and consider the Fourier transform of the complex measure $\nu(\mathrm{d}x) = f(x) ~\mu(\mathrm{d}x)$: \begin{align} \hat{\nu}(\xi) &= \int_{-\infty}^\infty \exp(-2\pi ix\xi) f(x) ~\mu(\mathrm{d}x) \\
&= \int_{-\infty}^\infty \exp(-2\pi i x\xi) f(x) \sum_{n=0}^{N-1} \delta_{n/N}(\mathrm{d}x) \\
&= \sum_{n=0}^{N-1} \exp(-2\pi i \xi n / N) f(n / N) \end{align}

The discrete Fourier transform is symmetric in the sense that $\hat{\nu}(\xi + N) = \hat{\nu}(\xi)$.
By direct calculation, \begin{align} \hat{\nu}(\xi + N) &= \sum_{n=0}^{N-1} \exp(-2\pi i (\xi + N) n / N) f(n / N) \\ &= \sum_{n=0}^{N-1} \exp(-2\pi i \xi n / N) \exp(-2\pi i n) f(n / N) \\ &= \sum_{n=0}^{N-1} \exp(-2\pi i \xi n / N) f(n / N) \\ &= \hat{\nu}(\xi). \end{align}

Let $f: [-T/2, T/2]\to\mathbb{C}$ be an integrable function with Fourier expansion given by $f(x) = \sum_{n=-\infty}^\infty c_n \tilde{e}_n(x)$ where $\tilde{e}_n(x) = \exp(2\pi i n x / T) / \sqrt{T}$. Then \begin{align} \frac{\mathrm{d}}{\mathrm{d}x} f(x) &= \sum_{n=-\infty}^\infty 2\pi c_n i \frac{n}{T} \tilde{e}_n(x) \\ &= \sum_{n=-\infty}^\infty \tilde{c}_n \tilde{e}_n(x), \end{align} where $\tilde{c}_n = 2\pi c_n i n / T$.
There are several arguments that could be made to prove this relationship; here is one. The definition of the Fourier transform is, \begin{align} \hat{f}(\xi) = \int_{-\infty}^{\infty} f(x) \exp(-2\pi i \xi x) ~\mathrm{d}x. \end{align} Suppose we apply the Fourier transform instead to the function $f'$ as \begin{align} \hat{f}'(\xi) &= \int_{-\infty}^{\infty} f'(x) \exp(-2\pi i\xi x)~\mathrm{d}x \\ &= \left[f(x) \exp(-2\pi i \xi x)\right]_{-\infty}^\infty + 2\pi i \xi \int_{-\infty}^\infty f(x) \exp(-2\pi i \xi x)~\mathrm{d}x \\ &= 2\pi i \xi \hat{f}(\xi). \end{align} Now we recall that the Fourier series coefficients are related to the Fourier transform by the relationship $c_n = \hat{f}(n / T) / \sqrt{T}$. Applying this formula to the derivative we obtain, \begin{align} \tilde{c}_n &= \hat{f}'(n/T) / \sqrt{T} \\ &= 2\pi i \frac{n}{T} \hat{f}(n/T) / \sqrt{T} \\ &= 2\pi i \frac{n}{T} c_n. \end{align}

Let us demonstrate that the vectors $u_k = (\exp(2\pi i k n /N) ~:~ n=0, \ldots, N-1) \in \mathbb{C}^N$ form an orthogonal basis of $\mathbb{C}^N$. To demonstrate this, we begin by showing that such vectors are orthogonal: \begin{align} \langle u_k, u_l\rangle &= \sum_{n = 0}^{N-1} \exp(2\pi i k n /N) \exp(-2\pi i l n /N) \\
&= \sum_{n=0}^{N-1} \exp(2\pi i n (k -l) / N). \end{align} If $k=l$, we have \begin{align} \langle u_k, u_k\rangle &= \sum_{n=0}^{N-1} 1 \\
&= N. \end{align} Now suppose that $k\neq l$. In this case we obtain, via the geometric series, \begin{align} \langle u_k, u_l\rangle &= \sum_{n=0}^{N-1} \exp(2\pi i n (k -l) / N) \\
&= \sum_{n=0}^{N-1} \exp(2\pi i (k - l) / N)^n \\
&= \frac{1 - \exp(2\pi i (k - l))}{1 - \exp(2\pi i (k - l) / N)} \\
&= 0, \end{align} since $k - l \in \mathbb{Z}$. Since $\mathbb{C}^N$ is an $N$-dimensional vector space and $(u_k)_{k=0}^{N-1}$ are orthogonal, it follows that $(u_k)_{k=0}^{N-1}$ comprise a basis of $\mathbb{C}^N$.