Fourier Transformation

Let $f: [-\pi, \pi]: \rightarrow \mathbb{R}$ be a real function. As $f$ itself can be complicated, we want to decompose it into a linear combination of simpler functions.

Example. A typical family of simple functions are polynomials:

$$\{ 1, t, t^2, t^3, ... \}.$$

Under proper condition, e.g., if $f$ is infinitely differentiable, it can be indeed decomposed into a linear combination of polynomials, such as:

$$f = f(0) + f'(0) t + \frac{f''(t)}{2!} t^2 + ...$$

Problem

Here we study the problem of approximating $f$ with trigonometric functions:

Although $f: [-\pi, \pi]: \rightarrow \mathbb{R}$ is a function with output on $\mathbb{R}$, we view it as a function $[-\pi, \pi]: \rightarrow \mathbb{C}$ to take advantage of complex exponential. Now, we approximate $f$ with a set of sinusoids:

Observe that $\Gamma$ generalizes $\mathfrak{T}$, as for $\forall k \in \mathbb{N}$,

Define the span $S(\Gamma)$ as the set of all possible linear combinations of functions in $\Gamma$:

The goal is to find the closest function to $f$ in $S(\Gamma)$.

The key issues with the approximation are

1. How do we measure the closeness between two functions?

2. Under what condition, can $f$ be rewrite as a linear combination of functions in $\Gamma$?

3. What is the approximation error, between $f$ and the linear combination?

Norm

Despite the goal stated above, the closeness between $f$ and a function in $S(\Gamma)$ has not yet been defined. This raises the question of measuring the distance between two functions in $[-\pi, \pi] \rightarrow \mathcal{C}$.

In $\mathbb{R}^n$, the Euclidean distance between two vectors $u, v$ is defined as

If we define $w = u - v$, then the problem of measuring the distance between two vectors reduces to the one of measuring the length of a vector

In a similar manner, if we view a function $h: [-\pi, \pi] \rightarrow \mathcal{C}$ as an (uncountable) infinite dimension vector, it is natural to defined its length

Remark:

1. $|| h ||^2$ needs to be integrable.
2. Verify that $|| \cdot ||$ is a norm.

As $f - g$ is also a function in $[-\pi, \pi] \rightarrow \mathcal{C}$, the distance between two functions $f$ and $g$ is given by

Remark:

1. $|| f - g ||^2$ needs to be integrable.
2. The integration operation is required to be linear.

Hermitian Product

To simplify the expansion of $||f - g||$, we introduce another operation, termed Hermitian product, as follows:

The operation is not symmetric. By definition,

$\left< g, f \right>_H$ is the complex conjugate of $\left< f, g \right>_H$:

For any $c \in \mathbb{C}$, it holds that

Now the expansion of $||f - g||$ is simplified as

Geometric Interpretation

We have just introduced the notation of Hermitian product to simplify the expression. Its "geometric" interpretation is related to the idea of "projection". We start by reviewing the ideas of "Projection, Dot Product and Orthogonality" in $\mathbb{R}^2$.

Projection in $\mathbb{R}^2$. Given $u, v \in \mathbb{R}^2$, the projection of $u$ to $v$ is the vector in the subspace

$$S(v) \doteq \{ c \cdot v : c \in \mathbb{R} \}$$

that is closest to $u$.

Dot Product in $\mathbb{R}^2$. Given $u, v \in \mathbb{R}^2$, their dot product is defined as

$$\left< u, v \right> = u_1 v_1 + u_2 v_2.$$

The projection of $u$ to $v$ (closest vector to $u$ in $S(v)$) is given by

$$\frac{1}{ ||v||^2 } \left< u, v \right> \cdot v = \frac{ \left< u, v \right> }{ ||v|| } \cdot \frac{ v }{ ||v|| }.$$

The first term of the final product $\frac{ \left< u, v \right> }{ ||v|| } = \frac{ ||u|| \cdot ||v|| \cdot \cos \angle (u, v) }{ ||v|| } = ||u|| \cdot \cos \angle (u, v)$ gives the length of $u$'s projection to $v$, and the second term $\frac{ v }{ ||v|| }$ is a unit vector that shares the same direction as $v$.

Orthogonality in $\mathbb{R}^2$. Given $u, v \in \mathbb{R}^2$, they are orthogonal if the projection of $u$ to $v$ is $\vec 0$. In this case,

$$\left< u, v \right> = 0.$$

We can extend these ideas to $[-\pi, \pi] \rightarrow \mathbb{C}$.

Projection

Given $f, g:[-\pi, \pi] \rightarrow \mathcal{C}$, the projection of $f$ to $g$ is the function in the linear span of $g$

that minimize $||f - c \cdot g||, \forall c \in \mathbb{C}$.

Hermitian Product

Hermitian product is related to projection and arises naturally when we try to solve

or equivalently,

Expanding $||f - c \cdot g||^2$ and let $c = x + iy$, $\left< g, f \right>_H = a + i b$, we get

Remark: The derivation above requires the integration operation to be linear.

Taking the derivate of RHS with respect to $x$, setting it to zero and assuming that $||g|| \neq 0$, we see

Similarly,

Combined, $c$ is given by

This implies that

Now it is clear that the Hermitian product computes the coefficient for the projection of $f$ to $g$, scaled by a factor of $1/ ||g||^2$. When $|| g ||$ has unit length,

The Hermitian product $\in \mathbb{C}$ is the just the coefficient for the projection.

Orthogonality

Given $f, g:[-\pi, \pi] \rightarrow \mathcal{C}$, $f$ is orthogonal to $g$ if the projection of $f$ to $g$ is the zero function, i.e., the closest function (measured by $|| \cdot ||$) to $f$ in the linear span $S(g)$ is the constant function zero. It holds that, either $||g||^2 = 0$ or

In both cases,

Properties of $\Gamma$

We are now ready to discuss the properties of $\Gamma = \{ 1, \exp(it), \exp(-it), \exp(i2t), \exp(-i2t), ... \}$.

1. For $k \in \mathbb{Z}$,

   $$|| \exp(ikt) || = \sqrt{ \int_{ [-\pi, \pi] } \overline{\exp(ikt) } \exp(ikt) \ } = \sqrt{2 \pi }.$$

2. For $k, l \in \mathbb{Z}$, $k \neq l$, $\exp(ikt)$ and $\exp(ilt)$ are orthogonal.

   $$\begin{aligned} \left< \exp(ikt), \exp(ilt) \right>_H &= \int_{ [ -\pi, \pi] } \exp(-ikt) \cdot \exp(ilt) \\ &= \int_{ [ -\pi, \pi] } \exp(i (l - k) t) \\ &= \frac{1}{ i(l - k) } \exp(i (l - k) t) \mid_{- \pi}^\pi \\ &= 0. \end{aligned}$$

If we normalize the function in $\Gamma$ by $1 / \sqrt{2 \pi}$, then each function has norm 1. We call this family an orthonormal family, and rewrite it as

where $e_0 = 1$, and for $k \in \mathbb{N}$,

• $e_{2k + 1} = \exp(ikt) / \sqrt{2 \pi}$;

• $e_{2k + 2} = \exp(- ikt) / \sqrt{2 \pi}$.

Approximating $f$ with $\mathfrak{F}$

As discuss before, we have construct an orthogonal family of $\mathfrak{F}$, such that

1. $||e_i|| = 1$ for $e_i \in \mathfrak{F}$.
2. $\left< e_i, e_j \right>_H = 0$ for $e_i, e_j \in \mathfrak{F}, e_i \neq e_j$.

Definition. Define $S(\mathfrak{F}_k)$ the span of the first $k + 1$ elements in $\mathfrak{F}$:

Theorem. The closest function to $f$ in $S(\mathfrak{F}_k )$, denoted as $g_k$, is given by

$$g_k \doteq \sum_{i = 0 }^k a_i \cdot e_i.$$

where $a_i \doteq \left< e_i, f \right>_H, 0 \le i \le k$.

Remark: implicitly, we assume that $f^2$, $\bar e_i f$ is integrable.

Proof: For $0 \le i \le k$, it holds that

Hence,

Let

be a function in $S(\mathfrak{F}_k )$. Then,

It holds that

Similarly, $\left< g_k - f_k, f - g_k \right>_H = 0$. So,

which is minimized when $f_k = g_k$.

$\square$

Corollary. (Bessel Ineuqality).

$$\sum_{i = 0}^\infty ||a_i||^2 \le ||f||^2.$$

Proof. We see that

Therefore,

Taking the limit of $k$ we get the desired result.

$\square$

The function series $g_1, g_2, g_3, ...$ is called a Cauchy series, as $\forall \epsilon > 0$, $\exists N \ge 0$, $\forall N \le i < j$, it holds that

Suppose that we are using some kind of integration and let $I^2([-\pi, \pi])$ be the set of square integrable functions. Further, assume that $g_1, g_2, g_3, ...$ are also elements in $I^2([-\pi, \pi])$. We are interested in

Whether a Cauchy series in $I^2([-\pi, \pi])$ converges to a function in $I^2([-\pi, \pi])$?

Define

It is important that $g \in I^2([-\pi, \pi])$, as we need the length of $|| g ||$ to be well-defined. Further, $f - g$ should also be in $I^2([-\pi, \pi])$.

However, if we are using Riemann integration, the answer is no. Let $r_1, r_2, ....$ be the rational number in the interval of $[0, 1]$ and define

Then $h_i \in I^2([-\pi, \pi])$ but $\lim_{i \rightarrow \infty} h_i$ is not Riemann integrable, hence not in $I^2([-\pi, \pi])$.

If we are using Lebesgue integration, the answer is yes.

Fact. If we are using Lebesgue integration, then $I^2([-\pi, \pi])$ is complete, i.e., if $g_1, g_2, ..., \in I^2([-\pi, \pi])$ is Cauchy, then $\lim_k g_k \in I^2([-\pi, \pi])$.

Approximating Error

It is left to study the error of approximating $f$ with $g$.

Lemma. Cauchy-Schwartz Inequality. Let $h_1, h_2 \in I^2([-\pi, \pi])$, then

$$| \left< h_1, h_2 \right>_H | \le ||h_1|| \cdot ||h_2 ||$$

Proof. If $||h_2|| = 0$, then $h_2 = 0$ almost everywhere and the case is trivial. Otherwise, $\forall c \in \mathbb{C}$, we have

Let $c = \frac{1}{ ||h_2||^2 } \cdot \left< h_2, h_1 \right>_H$, then

$\square$

Lemma. $\forall i \in \mathbb{N}$, $\left< e_i, g \right>_H =a_i$.

Proof. By Cauchy-Schwartz inequality,

By Fatou's lemma,

Finally,

$\square$

Remark: the above proof involves the operation of exchanging the order of two limiting operations, namely $\lim$ and $\int$. Exchanging order like this is dangerous for Riemann integration, but we can do it safely under Lebesgue integration, under proper condition. Here we use Fatou's lemma.

By the above lemma, the function $g$ has an important property, such that $\forall i \in \mathbb{N}$,

Lemma. Let $h \in I^2([-\pi, \pi])$. If $\forall i \in N$,

$$\left< e_i, h \right>_H = 0,$$

then $h = 0$ almost everywhere.

Proof. First, we assume that $h$ is a continuous function on $[-\pi, \pi]$. If $h \not\equiv 0$, then $|h(x)|$ achieves maximum value at some point $x^* \in [-\pi, \pi]$. Without lose of generality, we assume that

By continuity of $h$, $\exists \delta \in (0, \pi)$, such that $h(x) > M / 2$ in the interval

We will capture the maximum value of $f$, by taking Hermitian product of $f$ with a signal function that

1. is a linear combination of functions in $\mathfrak{F}$;
2. is $\ge 1$ in $I$;
3. is $< 1$ in $[-\pi, \pi] \setminus I$.

The signal function is given by

Observe that $s$

1. achieves maximum value $s(x^*) = 2 - \cos \frac{\delta}{2}$;
2. is $\ge 1$ for $x \in I$;
3. has period $4 \pi$.

Hence, it increases on the interval $[x^* - 2\pi, x^*]$ and decreases on $[x^*, x^* + 2\pi]$. So

4. $s(x) < 1$ for $x \in [-\pi, \pi] \setminus I$.

For $n \ge 1$, $s^n(x)$ is also a linear combination of functions in $\mathfrak{F}$. It always holds that $\left< s^n(x), f \right>_H \in \mathbb{R}$ and by assumption on $f$, it holds that

But this is impossible. By monotonicity of integration,

Define

Then $|I'| \ge \delta / 2$ and $m \doteq \min_{x \in I'} s(x) > 1$.

This implies as $n \rightarrow \infty$,

which is a contradiction.

Next, we consider the general case of $h \in I^2([-\pi, \pi])$. Define

The function is absolutely continuous on $[-\pi, \pi]$. Moreover, $w(0) = 0$ and by assumption, $w(\pi) = \left< e_0, h \right>_H = 0$. For $k \in \mathbb{N}$, integrating by part gives

Similarly, we can prove that $\left< e_{2k + 2}, w \right>_H = 0$.

Hence, $\forall k \ge 1$, $\left< e_k, w \right>_H = 0$. But it is not guaranteed that $\left< e_0, w \right>_H = 0$. To fix this, we construct another function

where $B = \left< e_0, w \right>_H$ is a constant. It holds that

1. $\forall k \ge 1$, $\left< e_k, W \right>_H = \left< e_k, w \right>_H - \left< e_k, B \right>_H = - B \cdot \left< e_k, e_0 \right>_H = 0$.
2. $\left< e_0, W \right>_H = \left< e_0, w \right>_H + \left< e_0, B \right>_H = B - B \cdot \left< e_0, e_0 \right>_H = 0$.

By previous result, $W(x) \equiv 0$ and $w(x) \equiv B$. This implies

$\square$