Fourier Series and Transform

Editovat

Fourier analysis

Study of how general functions (e.g., on $R$ ) can be approximated by sums of simpler (e.g., trigonometric) functions.
Fourier’s original motivation was to solve the heat equation, a partially differentiable equation.
- A partially differentiable equation (PDE) involves multiple variables and one or more of their derivatives.
- Example: I want to know what happens, when I put two rods of different temperatures into contact.

Fourier series

Fourier series (FS)

Series expansion (CZ: rozvinutí nekonečné řady) of a periodic function into a sum of basis functions.

For basis functions, it uses $sin$ and $cos$ functions with a whole number frequency.
Foundation for Fourier analysis and expansion of periodic functions in general.
Simple mathematical tool for approximation of periodic functions.
The $F (k)$ coefficients are called frequency spectrum.
Each $F (k)$ coefficient is the projection of the $k$ -th basis function onto $f$ .
It answers the question: "How important is this basis function in the grand scheme of $f$ ?"
Typically, we use a $lo g$ scale for visualization of the coefficients.

Fourier series on $π$ -periodic functions

Any $π$ -period function $f$ can be expanded in the following way:

f (x) a_{k} b_{k} = k = 0 \sum \infty (a_{k} cos (k x) + b_{k} sin (k x)) where = \frac{⟨ f ( x ) , cos ( k x )⟩}{⟨ cos ( k x ) , cos ( k x )⟩} = \frac{⟨ f ( x ) , sin ( k x )⟩}{⟨ sin ( k x ) , sin ( k x )⟩}

$k$ — frequency at which $sin$ and $cos$ oscillate
$a_{k}$ — coefficients of even parts of $f$
$b_{k}$ — coefficients of odd parts of $f$

Fourier series on L-periodic functions

Similar to $π$ -periodic functions, but we multiply $k$ by $\frac{2 π}{L}$ , where $L \in R$ :

f (x) a_{k} b_{k} = k = 0 \sum \infty (a_{k} cos (\frac{2 π}{L} k x) + b_{k} sin (\frac{2 π}{L} k x)) where = \frac{⟨ f ( x ) , cos ( \frac{2 π}{L} k x )⟩}{⟨ cos ( \frac{2 π}{L} k x ) , cos ( \frac{2 π}{L} k x )⟩} = \frac{⟨ f ( x ) , sin ( \frac{2 π}{L} k x )⟩}{⟨ sin ( \frac{2 π}{L} k x ) , sin ( \frac{2 π}{L} k x )⟩}

Complex Fourier series on $2 π$ -periodic functions

With complex numbers the formula becomes:

f (x) x F (x) = k = - \infty \sum \infty F (k) \cdot e^{ik x} where \in ⟨ - π, π ⟩ = \frac{⟨ f ( x ) , e ^{ik x} ⟩}{⟨ e ^{ik x} , e ^{ik x} ⟩}

When we express $F (k)$ out of the above formula, it converts time into frequency:

F (k) = \frac{1}{2 π} \int_{- π}^{π} f (x) \cdot e^{- ik x} d x where k \in Z

Complex Fourier series on L-periodic functions

We multiply $k$ by $\frac{2 π}{L}$ and adjust the scaling factor and integral boundaries, where $L \in R$ :

Expansion/Frequency → Time:

f (x) = k = - \infty \sum \infty F (k) \cdot e^{- \frac{2 π}{L} ik x} where x \in ⟨ - \frac{L}{2}, \frac{L}{2} ⟩

Time → Frequency:

F (x) = \frac{1}{L} \int_{- \frac{L}{2}}^{\frac{L}{2}} f (x) \cdot e^{- \frac{2 π}{L} ik x} d x where k \in Z

Why use complex numbers in the Fourier series and Fourier transform?

They simplify the formula:
- $cos (k x) + i \cdot sin (k x) = e^{ik x}$ (Euler’s formula)
With them, FT is can be solved linearly and expressed using matrix multiplication. Without them, it’s an optimization problem that must be solved numerically.
- If we used real numbers and, for example, $sin (km - α)$ as the basis function, we would not be able to use matrix multiplication and would have to find $α$ numerically.
Complex numbers also symbolize rotation, which makes for a nice intuitive explanation (see below).

Proof of orthogonality of the Fourier series

TODO

Gibbs phenomenon

Functions with discontinuities are hard to be approximated with Fourier series as $sin$ and $cos$ are both smooth.

Fourier transform

Fourier transform (FT)

Fourier transform $F$ is a function taking a signal (a function $f$ of time) and converting it to the frequency domain (function $F$ of frequencies).

FT is a generalization of FS. It’s derived from L-periodic complex FS with $L \to \infty$ .
FS handles only periodic signal. FT handles aperiodic signal.
It’s total. Lossless. Doesn’t throw away any information. It’s invertible. A bijection. A linear mapping.
It a tool for frequency analysis.

Inverse transform (frequency → time):

f (x) = \frac{1}{2 π} \int_{- \infty}^{\infty} F (ω) \cdot e^{iω x} d ω where x \in (- \infty, \infty)

Forward transform (time → frequency):

F (ω) = \int_{- \infty}^{\infty} f (x) \cdot e^{- iω x} where ω \in (- \infty, \infty)

Commonly:

F (ω) G (ω) = F (f (x)) = F (g (x))

Coefficients of the Fourier transform

Each coefficient $F (ω)$ is associated with a basis function $e^{iω x}$ oscillating at frequency $ω$ .
$F (ω) = A_{ω} \cdot e^{i ϕ_{ω}}$ is simply a complex number, where:
- amplitude $A_{ω}$ — strength of basis function $e^{iω x}$
- phase $ϕ_{ω}$ — controls the phase shift of basis function $e^{iω x}$

Spectral density

Plot of $F (ω)$ for $ω \in (- \infty, \infty)$ .

Function pairs in the Fourier transform

FT of the rectangle function is sinc.
FT of a Gaussian is a (different) Gaussian.

Intuitive explanation of the Fourier transform [2]

Complex numbers describe rotation, therefore multiplying $f$ by a set of complex numbers "winds $f$ up" around a circle.
Sampling this wound-up version of $f$ (whether using an integral or sum) means calculating the center of mass of the wound up version.
When the center of mass is far away from the origin, the wound-up $f$ "aligns" with itself, meaning there is a strong correlation between $f$ and the sinusoid given by the "winding" frequency.
- Except in FT, there is no division by the length of the studied interval, so it’s a "scaled center of mass". This has the effect that the more persistent a frequency is, the higher its spike.

Note	The "winding" is clockwise by convention. That’s why there’s a $- i$ in the equation.

Properties of the Fourier transform

Shift affects only the phase

$F [f (x - a)] (ω) = e^{- 2 π \cdot i \cdot aω} F (ω)$
Scaling — Narrowing in the time domain causes widening in the frequency domain, and vice versa:\

$F [f (a x)] (ω) = \frac{1}{∣ a ∣} F (\frac{ω}{a})$
Derivative enhances high frequencies:

$F [\frac{\partial}{\partial x} f (x)] = i \cdot ω \cdot F (ω) F [\frac{\partial}{\partial ^{2} x} f (x)] = i \cdot ω^{2} \cdot F (ω)$

Convolution theorem (CZ: věta o konvoluci)

Given two signals $f$ and $g$ and their Fourier transforms $F$ and $G$ , respectively, the following holds:

$F (f * g) = F \cdot G$
$F (f \cdot g) = F * G$

where ' $*$ ' stands for a convolution and ' $\cdot$ ' for point-wise multiplication.

Discrete time Fourier Transform (DTFT)

We sample the time domain:

TODO

Discrete Fourier transform (DFT)

DTFT with a limited range
$F (0)$ is also called "direct current (DC)", "mean", or "normalizovaný součet"
- prakticky má omezený rozsah, matematicky je periodická a dokonečna se opakuje

Vlastnostni DFT

V diskrétním světě nefunguje škálování, máme jen převzorkování.
Periodicita + můžeme sáhnout mimo a bude tam hodnota
vstupní signál se tváří periodicky, takže může vzniknout "falešná hrana"
- řešení - rozmažeme hraje - Hammingovo okno (děláme konvoluci ve frekvenční doméně, takže násobíme v původní doméně)
zajímají nás nízké frekvence, proto v praxi je ve vizualizacích nula uprostřed
hermitovská symetrie
konvoluční teorém - platí, ale potřeba přidat normalizaci
kronekrovo delta
DFT a IDFT je efektivnější než konvoluce, ale musíme mít signál rozumné délky (na délce třeba 5 se to nevyplatí)
stretch
TODO: proč musím snížit amplitudu o 1/sqrt(p)?
u piana a hlasů je v té vizualizaci vpravo dole jen amplituda?
mixážní pulty umožňují omezit/zvýšit konkrétní rozsahy frekvencí
fast fourier transform
rekurzivní, rozděl a panuj
využívá vlastnosti DFT (stretch, shift, linearity), vlastně vůbec nepočítá vzoreček DFT
…ale postupů je víc
na dně vracím vstup

1D Fourier transform formula summary

Low-pass filter

Linear filter
Low frequencies pass through

High-pass filter

Linear filter
High frequences pass through

Sampling

Abych mohl vzorkovat, musí mít spojitá funkce omezenou nejvyšší frekvenci. (Jinak se frekvenční spektrum ořízne.)
Vzorkovací frekvence je zespodu omezená tím, že nechceme ztratit informace, a seshora smysluplností - nechceme plýtvat místem a výkonem.
Vzorkováním vzniká omezený ale periodický frekvenční prostor.
Nyquist-Shannon theorem
Prefiltering jako řešení aliasingu
Resampling
Warping
Post-filtering - supersampling

Fourier Transform in 2D

Fourier transform in 2D

Forward continuous:

F (u, v) = \int_{- \infty}^{\infty} \int_{- \infty}^{\infty} f (x, y) \cdot e^{- i \cdot 2 π \cdot (ux + v y)} d x d y

Inverse continuous:

f (x, y) = \int_{- \infty}^{\infty} \int_{- \infty}^{\infty} F (u, v) \cdot e^{i \cdot 2 π \cdot (ux + v y)} d u d v

Forward discrete (2D DFT) of image with $N \cdot M$ pixels:

F (u, v) = x = 0 \sum N - 1 y = 0 \sum M - 1 f (x, y) \cdot e^{- i (\frac{2 π}{N} ux + \frac{2 π}{M} v y)}

Inverse discrete (2D IDFT) of frequency domain with $N \cdot M$ values:

f (x, y) = u = 0 \sum N - 1 \frac{1}{NM} v = 0 \sum M - 1 F (u, v) \cdot e^{i (\frac{2 π}{N} ux + \frac{2 π}{M} v y)}

Frequency domain (FD) in 2D DFT

We only care about one period of FD. Thus, the FD "image" has the same size as the original.
We shift the image by $(\frac{N}{2}, \frac{M}{2})$ so that zero frequency is in the center (and not in the corner).
The FD has two components (real/imaginary, or magnitude/phase). Typically, we only display magnitude but phase still exists!
We show the FD magnitudes on a $lo g$ scale.

Visually, each $ω = (u, v)$ vector of FD represents a 2D sinusoidal function of $(x, y)$ . Magnitude of $ω$ is the frequency. Direction of $ω$ is the orientation of the "waves".

Questions

Explain the meaning of Fourier coefficients.: They measure the amount of correlation of a single basis function with the expanded function.
Prove that Fourier transform is a linear mapping.: TODO
Describe the spectral density plot.: TODO
Which frequencies dominate in the Gaussian plot?: TODO
Which operation in frequency domain corresponds to convolution in time domain?: Point-wise multiplication.
Which frequencies are enhanced if we apply a derivative to an input signal?: TODO
Define a discrete Fourier basis function with frequency k and overall length N.: TODO
Create a matrix that can perform forward Fourier transform for a signal of length $N = 2$ .: TODO
What is the product of the projection of an even function into a sin wave?: TODO
Why are the wide functions in time domain transformed into their narrow counterparts in frequency domain and vice versa?: TODO
Compare the complexity of standard DFT and FFT.: TODO
What happens in Fourier domain if the signal samples are interleaved with zeros?: TODO
Prove that DFT is a linear mapping.: TODO
Why does scaling not work in the case of DFT?: TODO
Explain the reciprocity of time and frequency domain.: TODO
Show an example of the aliasing effect.: TODO
Explain the difference between low-pass and high-pass filter.: TODO
What is a prefilter?: TODO
Give an example of $γ$ warping function.: TODO
Explain the relationship between DFT and DCT.: TODO
Describe the F-DCT algorithm and compute $F-DCT ([1, 6, 6, 1])$ .: TODO
Is there ever any reason to do a convolution in the frequency domain?: TODO

References

[1] David Svoboda, PV291 — Introduction to Digital Signal Processing, 2025
[2] 3Blue1Brown, But what is the Fourier Transform? A visual introduction., 2018
[3] 3Blue1Brown, But what is a Fourier series? From heat flow to drawing with circles, 2019
https://dsprelated.com/
https://www.youtube.com/playlist?list=PLMrJAkhIeNNT_Xh3Oy0Y4LTj0Oxo8GqsC
https://cbia.fi.muni.cz/software/ftutor2d.html
PV131 — Digitální zpracování obrazu
- Lecture 03 — Multi-dimensional Fourier Transform
https://www.robots.ox.ac.uk/~az/lectures/ia/lect2.pdf