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

by | Jan 12, 2021 | Math Lecture

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

#### 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=\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 $$H_{p_1 p_2}=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 \Rightarrow 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$$

1. It must first be proven that the closures of a function algebra is closed under absolute value, minimum, and maximum operations. To do this, it must be shown that $$f \in \bar{\mathcal{A}} \Rightarrow |f| \in \bar{\mathcal{A}}$$ by approximating the absolute value function on the interval $$[-||f||,||f||]$$ by a polynomial. According to the Weierstrass Approximation Theorem, the polynomials are dense in the space of real continuous function on an interval, and thus since $$|y|$$ is a continuous function, on $$[-||f||,||f||] \ \exists$$ a polynomial $$p(y)$$ that approximates it, in that $$\sup{|p(y)-|y||:|y|\leq ||f||}<\frac{\epsilon}{2}$$.

Letting $$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 the 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.
2. It must then be shown that $$\mathcal{A}$$ separates $$C^0M$$, in that 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$$. By Lemma 1, $$\forall p,q \in M, \ \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 \Rightarrow 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 \Rightarrow 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 \Rightarrow |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

1. Pugh, Real Mathematical Analysis, pp. 234-239.
2. Elias M. Stein & Rami Shakarchi, Real Analysis: Measure Theory, Integration, \& Hilbert Spaces. Princeton Lectures in Analysis, Vol. III, pp. 160,170,171.

Responses to this post:

# Blog Main

Featured Bundles

## All Categories

Math Resources

Student Tips

Math Learning

Math Test Preps

Math Lectures

Professional Math

Math Fun Facts

Math Blogs