Fourier and wavelet transforms
author:Andres Garcia Saravia Ortiz de Montellano
date: 23.11.2015
Representation of functions
incremental: true
Let $f:\mathbb{R}\rightarrow\mathbb{C}$
Maclaurin representation:
$$f(x) = a_0 + a_1 x + a_2 x^2 +\cdots $$
Fourier representation:
$$f(x) = a_0 + a_1 \cos{(w_1 x)} + \cdots + b_1 \sin{(w_1 x)} + \cdots$$
equivalently,
$$f(x) = a_0 + a_1 e^{i w_1 x} + a_2 e^{i w_2 x} + \cdots$$
Fourier representations
incremental: true
The Fourier representation looks different depending on the domain of the function $f:A\rightarrow\mathbb{C}$ , with $A$ being:
$\mathbb{R}$ : Real numbers
$\mathbb{T}_p$ : Circle of length $p$
$\mathbb{Z}$ : Integer numbers
$\mathbb{P}_N$ : Polygon of $N$ sides
Continuous Fourier Transform (CFT)
For functions defined on the real line $\mathbb{R}$ .
$f:\mathbb{R}\rightarrow\mathbb{C}$
$$
\begin{aligned}
f(x) &= \int_{-\infty}^\infty F(s) e^{2\pi i s x} ds \\
F(s) &= \int_{-\infty}^\infty f(x) e^{-2\pi i s x} dx \\
\end{aligned}
$$
Fourier Series
For functions defined on the integers on an interval $\mathbb{T}_p=[0,p)$ .
$g:\mathbb{T}_p\rightarrow\mathbb{C}$ with $g(p) = g(0)$
$$
\begin{aligned}
g(x) &= \sum_{k=-\infty}^\infty G(k) e^{2\pi ikx/p} \\
G(k) &= \frac{1}{p}\int_{0}^p g(x) e^{-2\pi ikx/p} dx \\
\end{aligned}
$$
Discrete Time Fourier Transform (DTFT)
For functions defined on the integers $\mathbb{Z}$ .
$\phi:\mathbb{Z}\rightarrow\mathbb{C}$
$$
\begin{aligned}
\phi(n) &= \int_{0}^p \Phi(s) e^{2\pi isn/p} ds \\
\Phi(s) &= \frac{1}{p}\sum_{n=-\infty}^\infty \phi(n) e^{-2\pi isn/p} \\
\end{aligned}
$$
Discrete Fourier Transform (DFT)
For functions defined on a polygon with $N$ vertices $\mathbb{P}_N = {0,1,2,\ldots, N-1}$ .
$\gamma:\mathbb{P}_N\rightarrow\mathbb{C}$ with $\gamma(N) = \gamma(0)$
$$
\begin{aligned}
\gamma(n) &= \sum_{k=0}^{N-1} \Gamma(k) e^{2\pi ikn/N} \\
\Gamma(k) &= \frac{1}{N}\sum_{n=0}^{N-1} \gamma(n) e^{-2\pi ikn/N} \\
\end{aligned}
$$
Parseval's identities
$$
\begin{aligned}
\int_{-\infty}^\infty f(x)\overline{g(x)}dx
&= \int_{-\infty}^\infty F(s)\overline{G(x)}ds,\ \ \mathbb{R} \
\int_{0}^p f(x)\overline{g(x)}dx
&= p \sum_{k=-\infty}^\infty F(k)\overline{G(k)},\ \ \mathbb{T}p \
\sum {n=-\infty}^\infty f(n)\overline{g(n)}
&= p \int_{0}^p F(s)\overline{G(x)}ds,\ \ \mathbb{Z} \
\sum_{n=0}^{N-1} f(n)\overline{g(n)}
&= N \sum_{k=0}^{N-1} F(k)\overline{G(k)},\ \ \mathbb{P}_N
\end{aligned}
$$
Discretization and periodization
A continuous function $f$ can be made discrete $\phi$ by $h$-sampling
$$\phi(n) = f(nh), n\in\mathbb{Z},\ h>0 $$
From a function $f$ , under some conditions, we can construct a periodic function $g$ by $p$-summation
$$g(x) = \sum_{m=-\infty}^\infty f(x-mp) $$
Poisson relations
incremental: true
$p$ -summation
$$g(x) = \sum_{m=-\infty}^\infty f(x-mp)
\implies G(k) = \frac{1}{p}F\left(\frac{k}{p}\right)$$
$p/N$ -sampling
$$\phi(n) = f\left(\frac{np}{N}\right)
\implies \Phi(s) = \sum_{m=-\infty}^\infty F\left(s - \frac{mN}{p}\right)$$
Poisson cube
Nyquist-Shannon sampling theorem
incremental: true
Assume that $f(t)$ is $\sigma$-bandlimited
$$|\omega|>\sigma \implies F(\omega)=0$$
Sample it with an interval $\Delta t$
$$g(n) \equiv f(n\Delta t)$$
Then, $f(t)$ can be uniquely reconstructed only when
$$2\sigma \Delta t <1$$
$$\sigma < \frac{1}{2\Delta t} \equiv \omega_{Nyq}$$
Example: single sinusoid
incremental:true
$$
\begin{aligned}
f(t) &= a_1\sin(2\pi \omega_1 t) \\
F(\omega)
&= \int_{-\infty}^{\infty}a_1\sin(2\pi \omega_1 t)e^{-2\pi i \omega t} dt\\
&= a_1\int_{-\infty}^{\infty}
\left(\frac{e^{2\pi i\omega_1 t} - e^{-2\pi i\omega_1 t}}{2i}\right)
e^{-2\pi i \omega t}dt\\
&= \frac{a_1}{2i}\left[\delta(\omega-\omega_1)
- \delta(\omega+\omega_1)\right]
\end{aligned}
$$
$$
P(\omega) \equiv \left|F(\omega)\right|^2= \left(\frac{a_1}{2}\right)^2\left[\delta(\omega-\omega_1)
- \delta(\omega+\omega_1)\right]^2$$
Example: single sinusoid
Example: gaussian noise
Example: Multiple sinusoids with noise
Example: Time-varying signal
Example: Time-varying signal 2
Short-time Fourier Transform (STFT)
incremental: true
Make Fourier Transform of short segments in the timeseries using a window function centered at $\tau$ , $w(t-\tau)$
$$\hat{F}(\omega, \tau) =
\int_{-\infty}^\infty f(t) w(t-\tau) e^{-2\pi i \omega t} dt$$
Problem: Choose an appropriate window width
Frequency vs. time resolution
Wavelet transforms
incremental: true
Idea:
Narrow windows for large frequencies (good time resolution)
Wide windows for small frequencies (good frequency resolution)
Choose a localized wave (mother wavelet) $\psi(t)$ and define
$$\psi_{a,b}(t)=\frac{1}{\sqrt{a}}\psi\left(\frac{t-b}{a}\right)$$
Wavelet transforms
incremental: true
Example: Mexican-hat wavelet
$$\psi(t) = \left(1-t^2\right)e^{-t^2/2}$$
$$\psi_{a,b}(t)=\frac{1}{\sqrt{a}}\psi\left(\frac{t-b}{a}\right)$$
Definition of wavelet transforms
incremental: true
Given $f\in L^2(\mathbb{R})$ , we define its continuous wavelet transform with respect to the wavelet $\psi$ as
$$\mathcal{W}{\psi}[f] (a,b) = \int {-\infty}^\infty f(t)\overline{\psi_{a,b}(t)}dt$$
For $\mathcal{W}_\psi[f]$ to be invertible we require
$$ 0 < C_{\psi}\equiv\int_{-\infty}^\infty
\frac{\left|\hat{\psi}(\omega)\right|^2}{\left|\omega\right|} d\omega
<\infty $$
Example: Time-varying signal CWT
incremental: true
Mexican hat CWT
Example: Time-varying signal CWT 2
incremental: true
Haar CWT
Morlet CWT
Example: Time-varying signal CWT 3
incremental: true
Morlet
Mexican-hat
Parseval's relation for wavelets
$$
\int_{-\infty}^\infty\int_{-\infty}^\infty \mathcal{W}\psi f (a,b)\overline{\mathcal{W} \psi g (a,b)} \frac{da db}{a^2} = C_{\psi}\langle f,g\rangle
$$
where
$$
C_\psi \equiv \int_{-\infty}^\infty \frac{|\hat{\psi}(\omega)|^2}{|\omega|}d\omega
$$
Inverse of a wavelet transform
incremental: true
$$f(t) = \frac{1}{C_\psi}\int_{-\infty}^\infty\int_{-\infty}^\infty \mathcal{W}\psif \psi {a,b}(t) \frac{da\ db}{a^2}$$
only when
$$ 0 < C_{\psi}\equiv\int_{-\infty}^\infty
\frac{\left|\hat{\psi}(\omega)\right|^2}{\left|\omega\right|} d\omega
<\infty $$
Discrete wavelet transform
incremental: true
Change the continuous version
$$\psi_{a,b}(t) = \frac{1}{\sqrt{a}} \psi\left(\frac{t-b}{a}\right),\ \ a,b\in\mathbb{R},\ a\neq 0 $$
to a discrete version
$$\psi_{m,n}(t)=2^{-m/2} \psi \left( 2^{-m} t - n \right),\ \ \ n,m \in \mathbb{Z}$$
When can we recover $f(t)$ from $\mathcal{W}_\psif $ ?
Orthonormal basis
Find $\psi_{m,n}$ such that they form a complete and orthonormal basis in $L^2(\mathbb{R})$ :
$$f(t) = \sum_{m,n=-\infty}^\infty \langle f,\psi_{m,n}\rangle\ \psi_{m,n}(t)$$
Multiresolution analysis (MRA)
incremental: true
MRA is really an effective mathematical framework for hierarchical decomposition of an image (or signal) into components of different scales (or frequencies).
Example application
Time-frequency analysis of solar $p$ -modes
F. Baudin, A. Gabriel, D. Gibert (1994)
Example application 2
Wavelets: a powerful tool for studying rotation, activity, and pulsation in Kepler and CoRoT stellar light curves
J. P. Bravo, S. Roque, R. Estrela, I. C. Leão, and J. R. De Medeiros (2014)
Thank you!
https://github.molgen.mpg.de/saravia/wavelets-SAGE
saravia@mps.mpg.de
ags3006@gmail.com
Orthogonality relations
$$\int_{-\infty}^\infty e^{2\pi i (x-x')}dx' = \delta(x)$$
$$\int_0^p e^{2\pi i x (k-l)/p}dx =
\begin{cases}
p &\mbox{if}\ \ k=l \\
0 &\mbox{otherwise}
\end{cases}
$$
$$\sum_{n=0}^{N-1} e^{2\pi i n (k-l)/N} =
\begin{cases}
N &\mbox{if}\ \ k = mN\ ,m\in\mathbb{Z} \\
0 &\mbox{otherwise}
\end{cases}
$$