Properties of the inner product:
Let f,g be functions on an interval [a,b]. The inner product of f and g is defined as (f,g) = \int_{a}^{b}f(x)g(x)dx. [show this is an inner product!]
Two functions f,g are orthogonal iff \left( f,g \right)=0. [show that the functions \cos \pi x and 1 are orthogonal on [-1,1]!]
The set of functions \{f_1, f_2,\ldots\} is orthogonal if every pair of functions in the set are orthogonal, \left( f_m,f_n \right)=0, for all m\neq n.
The norm of f on the interval [a,b] is defined as \|f\| = \sqrt{\left( f,f \right)} = \sqrt{\int_{a}^{b}f(x)^2dx} [Find the norm of \cos (\pi x/k)]
An orthogonal set \{\phi_1, \phi_2,\ldots\} is called orthonormal iff each element has norm 1, i.e. for all n, we have \|\phi_n\|=1. [show that the set {1, \cos \pi x, \sin \pi x} is orthogonal on [-1,1]]
We can transform any function \phi into a function of norm 1, by dividing by the norm (or normalizing – as you’d do to get the unit vector) \frac{\phi}{\|\phi\|} \quad\text{has norm 1}.
Given an orthogonal set of functions \{\phi_0, \phi_1,\ldots\}, we would like to represent a function f as a linear combination of these: f(x) = c_0\phi_0(x) + c_1\phi_1(x) + \ldots. We will need to figure out the coefficients.
It can be shown (show! this is in the lecture!) that each c_n = \frac{\left( f,\phi_n \right)}{\left( \phi_n,\phi_n \right)} = \frac{\left( f,\phi_n \right)}{\|\phi_n\|^2} = \frac{\int_{a}^{b}f(x)\phi_n(x)dx}{\int_{a}^{b}\phi_n(x)^2dx}.
If we use an orthonormal set, we get c_n = \frac{\left( f,\phi_n \right)}{1} = \left( f,\phi_n \right) = \int_{a}^{b}f(x)\phi_n(x)dx
The set \left\{1, \cos\frac{\pi x}{p}, \cos\frac{2 \pi x}{p}, \cos\frac{3 \pi x}{p}, \ldots, \sin\frac{\pi x}{p}, \sin\frac{2 \pi x}{p}, \sin\frac{3 \pi x}{p},\ldots \right\} is orthogonal on [-p,p]. [Test this! Use prev results]
A Fourier series is the expansion of a function f in terms of the above set, f(x) = \frac{a_0}{2} + \sum_{n=1}^{\infty}\left(a_n \cos\frac{n \pi x}{p} + b_n \sin\frac{n \pi x}{p} \right). Again, we need to figure out the coefficients. Using the formula we derived before, we get a_n = \frac{1}{p}\int_{-p}^{p}f(x)\cos\frac{n \pi x}{p}dx \quad \quad n=0,1,2,\ldots b_n = \frac{1}{p}\int_{-p}^{p}f(x)\sin\frac{n \pi x}{p}dx \quad \quad n=1,2,3,\ldots [do we really? test this!] The above can easily be obtained by noting that [show this!]
Let f, f' be piecewise continuous on [-p,p]. The Fourier series F(x) associated with f has the following convergence properties:
The right and left limits are notated as
Outside of [-p,p], the Fourier series continues periodically F(x \pm 2p) = F(x). (Remember, the Fourier series is written as the sum of trig functions, which are periodic). This would mean that F(p) = F(-p) = \frac{f(-p^+)+f(p^-)}{2}
If f is an even function, i.e. f(-x)= f(x), the Fourier series F(x) of f is the Fourier cosine series f(x) = \frac{a_0}{2} + \sum_{n=1}^{\infty} a_n \cos\frac{n \pi x}{p}.
If f is an odd function, i.e. f(-x)= -f(x), the Fourier series F(x) of f is the Fourier sine series f(x) = \sum_{n=1}^{\infty} b_n \sin\frac{n \pi x}{p}.
Given a function f on the interval [0,p], we can build a Fourier series from it by defining f on [-p,0] as:
Product of even and odd functions:
A function f can be split into its even f_e and odd f_o parts by the following:
Recall (from 1st year):
e^{i\pi} = e^{-i\pi} = -1 e^{ix} = \cos x + i \sin x e^{-ix} = \cos x - i \sin x \cos x = \frac{e^{ix} + e^{-ix}}{2} \sin x = \frac{e^{ix} - e^{-ix}}{2i}
The above can be used to write the Fourier series as f(x) = \sum_{n=-\infty}^{\infty} c_n e^{in\pi x / p}. The coefficients c_n are determined as c_n = \frac{1}{2p}\int_{-p}^{p}f(x) e^{-in\pi x/p}dx.
The Fourier transform \mathcal{F}(a) of a function f(x) on (-\infty, \infty) is defined as \mathcal{F}_f(a) = \int_{-\infty}^{\infty}f(x)e^{iax}dx.
The Fourier transform only exists if
The inverse Fourier transform goes from F(a)=\mathcal{F}_f(a) to f(x): f(x) = \frac{1}{2\pi} \int_{-\infty}^{\infty}F(a)e^{-iax}da if f is continuous at t.
The inverse Fourier transform \mathcal{F}^{-1}(\mathcal{F}(a)) = \frac{1}{2\pi} \int_{-\infty}^{\infty}F(a)e^{-iax}da = f(x) if f is continuous at t.
If f and f' are piecewise continuous and absolutely integrable, then \mathcal{F}(f'(x))=-ia\mathcal{F}(f(x)) and if f^{(n)} is piecewise continuous and absolutely integrable, then \mathcal{F}(f^{(n)}(x))=(-ia)^n\mathcal{F}(f(x)).
For a given period a, the Fourier transform is the sum of all the complex values that represent the polar co-ordinates (\theta, r) = (x, f(x)). The inverse transform, given a value x, recovers f(x) by taking the sum of the Fourier transform over all periods a.
The Fourier transform has largest magnitude (i.e., total radius) at a period a when the function is periodic with period a. This allows, for example, to decompose a time series into the component frequencies: the dominant frequencies are where the time series has the strongest periodic signal.
In the discrete Fourier transform, this is more intuitive, as the e^{-i\tfrac{2\pi}{N}nm} term corresponds to a rotation a lot more obviously.
The Fourier sine and cosine transforms are defined as \mathcal{F}_S(f(x)) = \int_{0}^{\infty}f(x)\sin ax dx \mathcal{F}_C(f(x)) = \int_{0}^{\infty}f(x)\cos ax dx Both have inversion formulas \mathcal{F}_S^{-1}(f(x)) = \frac{2}{\pi} \int_{0}^{\infty}f(a)\sin ax da = f(x) \mathcal{F}_C^{-1}(f(x)) = \frac{2}{\pi} \int_{0}^{\infty}f(a)\cos ax da = f(x)
The transforms of derivatives are \mathcal{F}_S(f'(x))=-a\mathcal{F}_C(f(x)) \mathcal{F}_C(f'(x))=a\mathcal{F}_S(f(x))-f(0) These can be used to obtain identities for higher derivatives.
Suppose, for example, you have a PDE involving the function u(x,t) of the form ku_{xx} = u_t, with some initial (or boundary) conditions.
We denote U(a,t) as the Fourier transform of u(x,t).
For periodic functions f, f(x) = \sum_{n=-\infty}^{\infty} F(n) e^{in\pi x / p}, we say that f is specified analytically in the time domain, and after applying the analysis equation, we get F which is in the frequency domain. The coefficients can then be passed to the synthesis equation to obtain the series representation of f in the time domain.
When F(n) is real, the plot of F against n is called the amplitude spectrum. When F(n) is complex, the magnitude (r) spectrum and phase spectrum plot the components of the polar representation of F(n). The plot of F against n is called the amplitude spectrum.
The DFT of the sequence x_0, x_1, \ldots, x_{N-1} is \hat{x}_m = \sum_{n=0}^{N-1} e^{-i\tfrac{2\pi}{N}nm} x_n for m=0,\ldots,N-1 where N is usually a power of 2.
The inverse DFT is then \hat{x}_n = \frac{1}{N} \sum_{m=0}^{N-1} e^{i\tfrac{2\pi}{N}nm} \hat{x}_m
The DFT is essentially a discrete approximation of the Fourier inversion formula and the IDFT is a discretisation of the Fourier Transform.
TODO (Tom’s Notes)
An O(N \log N) algorithm to compute the FFT:
FFT([x0, x2, . . . , xN−2])FFT([x1, x3, . . . , xN−1])[0, 1, . . . , N/2 − 1]The key insights into the FFT algo are as follows: