Fourier and wavelet transforms

Andres Garcia Saravia Ortiz de Montellano
23.11.2015








Representation of functions

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

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

\( 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

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

\[ \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

plot of chunk unnamed-chunk-1

plot of chunk unnamed-chunk-2

Example: gaussian noise

plot of chunk unnamed-chunk-3

plot of chunk unnamed-chunk-4

Example: Multiple sinusoids with noise

plot of chunk unnamed-chunk-5

plot of chunk unnamed-chunk-6

Example: Time-varying signal

plot of chunk unnamed-chunk-7

plot of chunk unnamed-chunk-8

Example: Time-varying signal 2

plot of chunk unnamed-chunk-9

plot of chunk unnamed-chunk-10

Short-time Fourier Transform (STFT)

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

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

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) \]

plot of chunk unnamed-chunk-11

Definition of wavelet transforms

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

plot of chunk unnamed-chunk-12

Mexican hat CWT

Example: Time-varying signal CWT 2

Haar CWT

Morlet CWT

Example: Time-varying signal CWT 3

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

\[ f(t) = \frac{1}{C_\psi}\int_{-\infty}^\infty\int_{-\infty}^\infty \mathcal{W}_\psi[f](a,b) \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

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}_\psi[f](m,n) \) ?

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)

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!

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} \]