La matrice di Fourier è una matrice complessa simmetrica del tipo di Vandermonde che esprime in forma matriciale la trasformata discreta di Fourier (DFT).
Indice
1Definizione
2Proprietà
3Fattorizzazione della matrice di Fourier
4Bibliografia
5Voci correlate
6Altri progetti
7Collegamenti esterni
Definizione
Una trasformata discreta di Fourier (DFT) che trasforma una successione di N numeri complessi nella successione di N numeri complessi è espressa come una moltiplicazione tra matrici:
Esplicitamente:
dove è una radice dell'unità primitiva N-esima e le sue potenze , con , costituiscono tutte le radici N-esime dell'unità.
Nella formulazione standard si assume : in tal caso la matrice di Fourier è propriamente associata alla trasformata discreta di Fourier (DFT). In altre formulazioni si adotta la convenzione con , e in tal caso la matrice di Fourier, a meno del fattore , risulta associata all'inversa della trasformata discreta di Fourier (IDFT).
Proprietà
I vettori colonna e riga della matrice di Fourier sono ortogonali. In particolare, indicando con la matrice coniugata di :
La trasformata inversa si ricava mediante la matrice inversa:
Inoltre, la matrice di Fourier normalizzata secondo il fattore risulta essere una matrice unitaria:
Fattorizzazione della matrice di Fourier
La fattorizzazione della matrice di Fourier in matrici sparse, contenenti cioè un gran numero di zeri e quindi tali da ridurre l'onere computazionale, è alla base degli algoritmi più diffusi per il calcolo della DFT, noti come trasformata di Fourier veloce (FFT).
Il caso più semplice si ha quando l'ordine della matrice è un numero pari (N = 2n). L'idea di base è quella di esprimere la matrice di Fourier di ordine 2n in termini della matrice di Fourier di ordine n. In tal caso, per le note proprietà della radice dell'unità, risulta infatti:
relazione tra
La matrice di Fourier di ordine 2n risulta:
Indicando con la matrice di permutazione che riordina le colonne di anteponendo le colonne di indice pari () a quelle di indice dispari (), risulta:
Le prime n righe della sottomatrice di sinistra coincidono, per definizione, con quelle della matrice di Fourier di ordine n, mentre le ultime n righe della sottomatrice di sinistra coincidono anch'esse con quelle della matrice di Fourier di ordine n. Risulta infatti:
Le prime n righe della sottomatrice di destra coincidono con quelle della matrice prodotto fra la seguente matrice diagonale di ordine n e la matrice di Fourier di ordine n:
Le ultime n righe della sottomatrice di destra coincidono, a meno del segno, con le prime n. Risulta infatti:
Sulla base delle precedenti considerazioni, si può scrivere:
e quindi ():
Come esempio di fattorizzazione nel caso :
A seguito della fattorizzazione l'onere computazionale, inizialmente pari a , diventa pari a: . La matrice di permutazione ha un onere computazionale nullo. Il primo termine è relativo al doppio prodotto per la matrice di Fourier di ordine dimezzato. Il secondo termine è relativo al prodotto per la matrice diagonale ; il prodotto per la matrice si ottiene infatti da quello per mediante un semplice cambio di segno.
Se l'ordine iniziale è una potenza di due il processo di fattorizzazione può continuare fino ad esprimere la matrice iniziale di ordine N in funzione di N matrici di Fourier di ordine 1 (coincidenti con la matrice identità di ordine N). In tal caso, l'onere computazionale residuo è quello relativo alle m matrici diagonali ottenute dalla fattorizzazione: .
Bibliografia
Strang G. Introduction to Linear Algebra, 4th Edition, Wellesley - Cambridge Press, 2009.
Strang, G. Wavelet Transforms Versus Fourier Transforms. Bull. Amer. Math. Soc. 28, 288-305, 1993.