Trasformata di Fourier Discreta e Veloce

La trasformata di Fourier discreta (DFT) è uno degli strumenti fondamentali dell’analisi numerica, dell’elaborazione dei segnali e della matematica applicata. Ė un esempio perfetto di come una base ortonormale complessa possa essere utilizzata per cambiare rappresentazione di un vettore.
La DFT è semplicemente la proiezione di un vettore sulle basi ortonormali dei modi complessi, prospettiva geometrica che chiarisce la struttura della trasformata e spiega naturalmente proprietà come invertibilità, conservazione dell’energia e diagonalizzazione delle convoluzioni.

Consideriamo lo spazio vettoriale complesso $\mathbb{C}^{N}=\{\mathbf x:\{0,1,2,\dots,N-1\} \to \mathbb C\}$, di dimensione \(N\), dotato del prodotto scalare standard: \[ \langle \mathbf x, \mathbf y \rangle = \sum_{n=0}^{N-1} x_n \overline{y_n}. \] La DFT non fa altro che cambiare base in questo spazio. I vettori: \[ \mathbf v_k = \frac{1}{\sqrt{N}} \left(1, \omega^{-k}, (\omega^2)^{-k}, \dots, (\omega^{N-1})^{-k}\right), \] dove \[ \omega = e^{\frac{2\pi}{N}i} \] è la radice \(N\)-esima principale dell’unità, formano una base ortonormale di \( \mathbb{C}^N \), sono i modi complessi analoghi discreti delle funzioni \( e^{i k x} \) nella trasformata di Fourier continua.
Dato un vettore \(\mathbf x \in \mathbb{C}^N\), la trasformata di Fourier discreta è: \[\widehat{\mathbf x}=\left(\sum_{n=0}^{N-1} x_n,\sum_{n=0}^{N-1} x_n \, \omega^{-n},\dots,\sum_{n=0}^{N-1} x_n \, \omega^{-kn},\dots, \sum_{n=0}^{N-1} x_n \, \omega^{-(N-1)n} \right)\] ovvero \[ \widehat{x}_k = \sqrt{N} \, \langle \mathbf x, \mathbf v_k \rangle = \sum_{n=0}^{N-1} x_n \, \omega^{-nk}. \] La DFT fa le proiezioni di \(\mathbf x\) sui vettori della base ortonormale \(\{\mathbf v_k\}.\)

Indichiamo con \(F\) la matrice unitaria (a meno di un fattore \(1/\sqrt{N}\)) i cui vettori riga sono i \(\mathbf v_k\).

Graficamente

Poiché i \(\mathbf v_k\) formano una base ortonormale, vale la formula di ricostruzione: \[ \mathbf x = \sum_{k=0}^{N-1} \langle \mathbf x, \mathbf v_k \rangle \mathbf v_k. \] Sostituendo: \[ x_n = \frac{1}{N} \sum_{k=0}^{N-1} \widehat{x}_k \, \omega^{nk}, \] che è l'inversa della trasformata di Fourier discreta (IDFT).

Le proprietà che emergono naturalmente dalla visione ortonormale sono

• la matrice \(F\) è unitaria (a fattore \(1/\sqrt{N}\)) perché i vettori \(\mathbf v_k\) sono ortonormali,
• la norma, ovvero l’energia, si conserva sotto un cambio di base ortonormale (Parseval) \[ \sum_{n=0}^{N-1} |x_n|^2 = \frac{1}{N} \sum_{k=0}^{N-1} |\widehat{x}_k|^2, \]
• la convoluzione circolare diventa moltiplicazione punto a punto \[ \widehat{\mathbf x * \mathbf y} = \widehat{\mathbf x} \cdot \widehat{\mathbf y}. \] Infatti se \[ \mathbf x = (x_0, x_1, \dots, x_{N-1}), \qquad \mathbf y = (y_0, y_1, \dots, y_{N-1}) \] la convoluzione circolare \[ (\widehat{\mathbf x * \mathbf y} )_m = \sum_{n=0}^{N-1} \left( \sum_{k=0}^{N-1} x_k\, y_{(n-k)\bmod N} \right) e^{-i\frac{2nm\pi}{N}} \] che scambiando le somme diventa \[ (\widehat{\mathbf x * \mathbf y} )_m = \sum_{k=0}^{N-1} x_k \sum_{n=0}^{N-1} y_{(n-k)\bmod N} e^{-i\frac{2nm\pi}{N}} \] e se poi facciamo il cambio di variabile \(r = n-k\) \[ (\widehat{\mathbf x * \mathbf y} )_m = \sum_{k=0}^{N-1} x_k e^{-i\frac{2km\pi}{N}} \sum_{r=0}^{N-1} y_r e^{-i\frac{2rm\pi}{N}}. \]

La Trasformata di Fourier Veloce (FFT) è solo un algoritmo per calcolare la DFT in modo molto più efficiente. Alla base di elaborazione audio/video, compressione (JPEG, MP3), metodi spettrali per PDE, convoluzioni veloci, analisi di segnali e vibrazioni, usa simmetrie e ricorsione (algoritmo di Cooley–Tukey) per una complessità \(O(N \log N)\) invece di \(O(N²)\).

Come applicazione semplice ma interessante si può vedere come estrarre lo spettro delle frequenze in un segnale, ad esempio un segnale composto da tre sinusoidi e rumore.