A Tutorial in Data Science: Lecture 7 – The Elements of Fourier Analysis

by Justin Petrillo | Jan 12, 2021 | Math Lecture

Table of Contents

Fourier Analysis is the decomposition of any square-integrable functions into an infinite series of trigonometric functions. Here we show that the trigonometric polynomial functions are dense in the space of periodic continuous functions, and thus can be used as good approximations. This implies that any repeating pattern-as-function, however complex, as long as having continuity, has a series of simple trigonometric functions that will approximate it within a given error-tolerance.

We begin thus with some definitions:

A subset $\mathcal{A} \subset C^0M=C^0(M,\mathbb{R})$ , the space of continuous real functions from any metric space $M$ , is a function algebra if it is closed under addition, scalar multiplication, and function multiplication, i.e. $f,g \in \mathcal{A}, c \ constant \Rightarrow f+g, cf, f g \in \mathcal{A}$ .
$\mathcal{A}$ vanishes at point $p$ if $\forall f \in \mathcal{A}, \ f(p)=0$ .
Note: $\mathcal{A}$ Non-Vanishing in $C^0M: \ \not\exists p \in M \ s.t \forall f \in \mathcal{A}, \ f(p)=0$ , i.e. $\forall p \in M \ \exists f \in \mathcal{A} \ s.t. \ f(p)\neq 0$ .
$\mathcal{A}$ separates points if $\forall p_1,p_2 \in M, \ p_1\neq p_2, \ \exists f \in \mathcal{A} \ s.t. \ f(p_1)\neq f(p_2)$ . \
Note: $\mathcal{A}$ Separates $C^0M: \ \exists$ a countable collection of ${f_i} \in \mathcal{A} \ s.t. \ {f_i}$ are dense in $C^0M$
a trigonometric polynomial is defined by:
$T(x)=a_0 + \sum_{k=1}^{n}a_k \sin kx + \sum_{k=1}^{n}a_k \cos kx$

Note: the function algebra of all trigonometric polynomials, $\mathcal{T}={T(x)}$ separates points of $[0,2\pi)$ and vanishes nowhere

The Stone-Weierstrass Theorem: If $M$ is a compact metric space and $\mathcal{A}$ is a function algebra in $C^0M$ that vanishes nowhere and separates points, then $\mathcal{A}$ is dense in $C^0M$

i.e. $(i) \nexists p \in M \ s.t. \ \forall f \in \mathcal{A} \ f(p)=0 \ \& \ (ii) \ \forall p_1,p_2 \in M, \ p_1\neq p_2, \ \exists f \in \mathcal{A} \ s.t. \ f(p_1)\neq f(p_2) \implies \ Given \ F \in C^0M, \ \forall \epsilon >0 \ \exists f \in \mathcal{A} \ s.t. \ \forall x \in M \ |F(x)-f(x)|<\epsilon$

Note: We can see immediately that $\mathcal{T}$ is dense in the periodic functions on $[0,2\pi) \mapsto S^1</strong>$

Lemma 1: If $\mathcal{A}$ vanishes nowhere and separates points then $\exists f \in \mathcal{A}$ with specified values at any pair of distinct points, i.e. $\forall c_1, c_2 \in \mathbb{R}, \ \forall p_1,p_2 \in M, \ p_1\neq p_2, \ \exists f \in \mathcal{A} \ s.t. \ f(p_1)=c_1 \ \& \ f(p_2)=c_2$

$\forall p_1, \ p_2 \in M, \ p_1\neq p_2$ since $\mathcal{A}$ vanishes nowhere, there must at least a function for each point not equal to 0 at that point, i.e. $\exists g_1,g_2 \ s.t. \ g_1(p_1)\neq 0 \neq g_2(p_2)$ . Since $\mathcal{A}$ is an algebra, $g=g_1^2+g_2^2 \in \mathcal{A}$ and is non-zero at either point, i.e. $g(p_1)\neq 0 \neq g(p_2)$ . Since $\mathcal{A}$ separates points, let $h \in \mathcal{A}$ be a separator of these two points, i.e. $h(p_1)\neq h(p_2)$ . Thus, there is a linear combination of $g$ and $gh$ with the specified values:

Letting $H=H_{p_1 p_2}=\begin{bmatrix}g(p_1) & g(p_1)h(p_1)\ g(p_2) & g(p_2)h(p_2)\end{bmatrix}, \ det H = g(p_1)g(p_2)(h(p_2)-h(p_1))\neq 0$ , so with $C= \begin{bmatrix} c_1 \ c_2\end{bmatrix}, \ \exists \Lambda=\begin{bmatrix} \zeta \ \nu\end{bmatrix} \ s.t. \ H \Lambda = C$ , i.e. there is a linear solution, implying that $f=\zeta g + \nu gh$ is the specified function with $f(p_1)=c_1 \ \& \ f(p_2)=c_2$ .

Lemma 2: The closure of a function algebra in $C^0M$ is a function algebra

$\forall g_n, f_n \in \mathcal{A}, \ g_n \rightarrow g \in \bar{\mathcal{A}}, f_n \rightarrow f \in \bar{\mathcal{A}}, \ \& \ c \in \mathbb{R}$ it follows that $c f_n \rightarrow cf, \ f_n+g_n \rightarrow f+g \ \& \ f_n g_n \rightarrow fg \implies cf, f+g, \ \& fg \in \bar{\mathcal{A}}$ , which is thus closed under addition, function multiplication, and scalar multiplication, and so a function algebra.

Proof of the Stone-Weierstrass Theorem: $Given \ F \in C^0M, \ \forall \epsilon >0 \ \exists G \in \mathcal{A} \ s.t. \ \forall x \in M, \ |F(x)-G(x)|<\epsilon$

Prove: $f \in \bar{\mathcal{A}} \implies |f| \in \bar{\mathcal{A}}$ by approximating the absolute value function on the interval $[-||f||,||f||]$ by a polynomial.

From the Weierstrass Approximation Theorem: since $|y|$ is a continuous function, on $[-||f||,||f||] \ \exists$ polynomial $p(y)$ that approximates it, in that $\sup{|p(y)-|y||:|y|\leq ||f||}<\frac{\epsilon}{2}$

The closures of a function algebra is closed under absolute value, minimum, and maximum operations.

Let $q(y)=p(y)-p(0)$ , which has a zero constant term, yet still approximates $|y|$ since $|p(0)-|0||<\sup{|p(y)-|y||:|y|\leq ||f||}<\epsilon/2$ from Weierstrass Approximation Theorem so $|q(y)-|y||=|p(y)-|y|-p(0)|< |p(y)-|y||+|p(0)-|0||<\epsilon/2 + \epsilon/2 =\epsilon \ \forall y \in [-||f||,||f||]$ . Writing $q(y)=\sum_{i=1}^n a_i y^i$ and $g(x)=q(f(x))$ as an approximation of $|f|$ , by Lemma 2 $f\in \bar{\mathcal{A}}$ is an algebra so $g \in \bar{\mathcal{A}}$ since $q(y)$ has no constant term and can thus be generated by the 3 closed function algebraic operations. With $x \in M \ \& \ y=f(x), |g(x)-|f(x)||=|q(y)-|y||<\epsilon, \ so |f|\in \bar{\mathcal{A}}$ by the sequence of $g_{\epsilon=1/n}$ approximations with $|f|=\lim_{n\rightarrow \infty} g_{1/n}$ . Since $\max(f,g)=\frac{f+g}{2}+\frac{|f+g|}{2} \ \& \ \min(f,g)=\frac{f+g}{2}-\frac{|f+g|}{2}, \ \max(f,g),\min(f,g) \in \bar{\mathcal{A}}$ and by repetition, so are the max \& min for a finite number of functions.

$\mathcal{A}$ separates $C^0M$ : Due to compactness of M, $\exists {p_i,q_i}$ for which the linear combination of the product of their separating and non-vanishing functions ( ${H_{p,q}}$ ) are dense in $C^0M$

$\forall p,q \in M$ , by Lemma 1, $\exists H_{p,q} \in \mathcal{A} \ s.t. \ H_{pq}(p)=F(p) \ \& \ H_{pq}(q)=F(q)$ .

(i) Fixing $p$ and letting $q$ vary, since $F, H_{p,q}$ are continuous (i.e. $C^0$ ), so is $Err_{p,q}=H_{p,q}-F$ , and thus because $Err_{p,q}(q)=H_{p,q}(q)-F(q)=0>-\epsilon, \ \exists U_q=\mathcal{N}{\delta}(q)$ neighborhood around q such that for $x\in U_q, \ Err{p,q}(x)=H_{p,q}(x)-F(x)>-\epsilon \implies H_{p,q}(x)>F(x)-\epsilon$ . Since $M$ is compact and $M\subset \cup_{q \in M} U_{q}, \exists Q_n={q_1, \cdots q_n}\subset M \ s.t. \ M \subset \cup_{i \leq n} U_{q_i}$ , a finite subcover. Defining $G_p(x)=\max{H_{p q_i}:1\leq i \leq n}, \ G_p \in \bar{\mathcal{A}}$ , since $G_p(x)=H_{p q_i}(x)$ for some $i, \ G_p(p)=F(p), \ \& \ \forall x \in M, \ x \in U_{q_i}$ for some $i, \ so \ G_p(x) \geq H_{p,q_i}(x)>F(x)-\epsilon$ .

(ii) Now repeating the above for variable $p$ , $G_p-F=Err_p=\underset{q}{\max}Err_{p,q}$ is continuous with $Err_p(p)=G_p(p)-F(p)=0<\epsilon, \ so \ \exists V_p=\mathcal{N}{\delta}(p)$ neighborhood around p such that for $x\in V_p, \ Err_p(x)=G_p(x)-F(x)<\epsilon \implies G_p(x){0\leq i \leq m} V_{p_i}$ , a finite subcover. Setting $G=\min{G_{p_i}: i \in \mathbb{N}, \ 1\leq i \leq m}, \ G \in \bar{\mathcal{A}}$ and since $G(x)=G_{p_i}(x)$ for some $i, \ G(p)=G_{p_i}=F(p), \ \& \ \forall x \in M, \ x \in V_{p_i}$ for some $i, \ so \ G(x) \leq G_{p_i}(x)<F(x)+\epsilon$ .

From $(i)$ since $\forall x \in M, G(x)=G_{p_i}(x)$ for some i and $G_{p_i}(x)>F(x)-\epsilon$ , therefore $G(x)>F(x)-\epsilon$ . Thus, from $(ii), \ F(x)-\epsilon < G(x) <F(x)+\epsilon \implies |F(x)-G(x)|<\epsilon$ .

A corollary of the Stone-Weierstrass Theorem: Any $2\pi$ -periodic continuous function of $x \in \mathbb{R}$ can be uniformly approximated by a trigonometric polynomial

\[T(x)=a_0 + \sum_{k=1}^{n}a_k \cos kx + \sum_{k=1}^{n}a_k \sin kx]\
$[0,2\pi)$ parameterizes the unit circle $S^1$ by $x \mapsto (\cos(x),\sin(x))$ . Since $S^1$ is compact, a $2\pi$ -periodic continuous function of $x \in \mathbb{R}$ is equivalent to a continuous function on $S^1$ . The trigonometric functions $\mathcal{T} \subset C^0S^1$ are an algebra. If $\forall s \in S^1 \ \forall T_1 \ s.t. \ T_1(s)=0, \exists T_2=T_1+\kappa \ s.t. \ T_2(s)\neq 0$ , so $\mathcal{T}$ vanishes nowhere. And, $\forall s_1,s_2 \in S^1, s_1\neq s_2 \exists T \in \mathcal{T} \ s.t. \ T(s_1)\neq T(s_2)$ so it separates points. Thus, by the Stone-Weierstrass Theorem, the trigonometric polynomials $\mathcal{T}$ are dense in $C^0S^1$ .

This result may be extended to any p-periodic function by changing the trigonometric polynomial class
\[T_p(x)=a_0 + \sum_{k=1}^{n}a_k \cos \frac{k}{r}x + \sum_{k=1}^{n}a_k \sin \frac{k}{r}x, \ r=\frac{p}{2\pi}]\

Fourier Analysis

The Trigonometric Functions $e^{inx}$ are an orthonormal basis to $L^2$ and so their linear combinations with $a_n=(f,e^{inx})=\frac{1}{2\pi}\int_{-\pi}^{\pi}f(x)e^{-inx}$ Fourier coefficients are dense, with the coefficients going to zero.

References

Pugh, Real Mathematical Analysis, pp. 234-239.

Elias M. Stein & Rami Shakarchi, Real Analysis: Measure Theory, Integration, \& Hilbert Spaces. Princeton Lectures in Analysis, Vol. III, pp. 160,170,171.