Matrice di Fourier

La matrice di Fourier è una matrice complessa simmetrica del tipo di Vandermonde che esprime in forma matriciale la trasformata discreta di Fourier (DFT).

Definizione

Una trasformata discreta di Fourier (DFT) che trasforma una successione di N numeri complessi $x_0,\dots ,x_{N-1}$ nella successione di N numeri complessi $X_0,\dots ,X_{N-1}$ è espressa come una moltiplicazione tra matrici:

$X={𝐅}_{N}x$

Esplicitamente:

${𝐅}_N=\left[\begin{array}{cccc}{\omega }_N^{0\cdot 0}& {\omega }_N^{0\cdot 1}& \dots & {\omega }_N^{0\cdot (N-1)}\\ {\omega }_N^{1\cdot 0}& {\omega }_N^{1\cdot 1}& \dots & {\omega }_N^{1\cdot (N-1)}\\ ⋮& ⋮& \ddots & ⋮\\ {\omega }_N^{(N-1)\cdot 0}& {\omega }_N^{(N-1)\cdot 1}& \dots & {\omega }_N^{(N-1)\cdot (N-1)}\end{array}\right]=\left[\begin{array}{c}{\omega }_N^{jk}\end{array}\right]j,k=0,1,\dots ,N-1$

dove ${\omega }_N$ è una radice dell'unità primitiva N-esima e le sue potenze ${\omega }_N^k$, con $k=0,1,...,N-1$, costituiscono tutte le radici N-esime dell'unità.

Nella formulazione standard si assume ${\omega }_N=e^{-2\pi i/N}$: in tal caso la matrice di Fourier è propriamente associata alla trasformata discreta di Fourier (DFT). In altre formulazioni si adotta la convenzione con ${\omega }_N=e^{2\pi i/N}$, e in tal caso la matrice di Fourier, a meno del fattore $1/N$, 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 ${\overline{𝐅}}_N$ la matrice coniugata di ${𝐅}_N$:

${\overline{𝐅}}_N=\left[\begin{array}{c}{\omega }_N^{-jk}\end{array}\right]$

risulta:

${\left({𝐅}_N{\overline{𝐅}}_N\right)}_{rs}=\sum _{k=0}^{N-1}{\omega }_N^{rk}{\omega }_N^{-ks}=\sum _{k=0}^{N-1}{\omega }_N^{k(r-s)}=\{\begin{array}{cc}N& r=s\\ \\ 0& r\ne s\end{array}$

Infatti, posto $q=r-s=0$:

$\sum _{k=0}^{N-1}{\omega }_N^{kq}=1+{\omega }_N^q+{\omega }_N^{2q}+\dots +{\omega }_N^{(N-1)q}$

da cui:

${\omega }_N^q\cdot \sum _{k=0}^{N-1}{\omega }_N^{kq}={\omega }_N^q+{\omega }_N^{2q}+{\omega }_N^{3q}+\dots +{\omega }_N^{(N-1)q}+{\omega }_N^{Nq}=1+{\omega }_N^q+{\omega }_N^{2q}+\dots +{\omega }_N^{(N-1)q}=\sum _{k=0}^{N-1}{\omega }_N^{kq}$

considerando il primo e l'ultimo termine:

$({\omega }_N^q-1)\cdot \sum _{k=0}^{N-1}{\omega }_N^{kq}=0$

che implica:

$\sum _{k=0}^{N-1}{\omega }_N^{kq}=0$

Pertanto si ha:

${𝐅}_N{\overline{𝐅}}_N=N{𝐈}_N$

dove ${𝐈}_N$ è la matrice identità di ordine $N$.

La trasformata inversa si ricava mediante la matrice inversa:

${𝐅}_N^{-1}=\frac{1}{N}{\overline{𝐅}}_N$

$x={𝐅}_N^{-1}X$

Inoltre, la matrice di Fourier normalizzata secondo il fattore $1/\sqrt{N}$ risulta essere una matrice unitaria:

${𝐔}_N={𝐅}_N/\sqrt{N}{𝐔}_N^{-1}={\overline{𝐔}}_N|\det ({𝐔}_N)|=1$

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 ${\omega }_8^k\text{ e }{\omega }_4^l$

${\omega }_{2n}^k\text{ con }k=0,1,\dots ,2n-1=\{\begin{array}{ccc}{\omega }_n^l& l=0,1,\dots ,n-1& \text{rispett. per }k=0,2,\dots ,2n-2\\ \\ {\omega }_n^l\cdot {\omega }_{2n}& l=0,1,\dots ,n-1& \text{rispett. per }k=1,3,\dots ,2n-1\end{array}$

La matrice di Fourier di ordine 2n risulta:

${𝐅}_{2n}=\left[\begin{array}{cccc}{\omega }_{2n}^{0\cdot 0}& {\omega }_{2n}^{0\cdot 1}& \dots & {\omega }_{2n}^{0\cdot (2n-1)}\\ {\omega }_{2n}^{1\cdot 0}& {\omega }_{2n}^{1\cdot 1}& \dots & {\omega }_{2n}^{1\cdot (2n-1)}\\ ⋮& ⋮& \ddots & ⋮\\ {\omega }_{2n}^{(2n-1)\cdot 0}& {\omega }_{2n}^{(2n-1)\cdot 1}& \dots & {\omega }_{2n}^{(2n-1)\cdot (2n-1)}\end{array}\right]=\left[\begin{array}{c}{\omega }_{2n}^{0\cdot k}\\ {\omega }_{2n}^{1\cdot k}\\ ⋮\\ {\omega }_{2n}^{(2n-1)\cdot k}\end{array}\right]=\left[\begin{array}{c}{\omega }_{2n}^{jk}\end{array}\right]\text{ con }j,k=0,1,\dots ,2n-1$

Indicando con ${𝐏}_{2n}$ la matrice di permutazione che riordina le colonne di ${𝐅}_{2n}$ anteponendo le colonne di indice pari ($k=0,2,\dots ,2n-2$) a quelle di indice dispari ($k=1,3,\dots ,2n-1$), risulta:

${𝐅}_{2n}\cdot {𝐏}_{2n}=\left[\begin{array}{ccc}{\omega }_n^{0\cdot l}& |& {\omega }_n^{0\cdot l}\cdot {\omega }_{2n}^0\\ {\omega }_n^{1\cdot l}& |& {\omega }_n^{1\cdot l}\cdot {\omega }_{2n}^1\\ ⋮& |& ⋮\\ {\omega }_n^{(2n-1)\cdot l}& |& {\omega }_n^{(2n-1)\cdot l}\cdot {\omega }_{2n}^{(2n-1)}\end{array}\right]\text{ con }l=0,1,\dots ,n-1$

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:

${\omega }_n^{n\cdot l}={\omega }_n^{0\cdot l}$

${\omega }_n^{(n+1)\cdot l}={\omega }_n^{1\cdot l}$

$\dots$

${\omega }_n^{(2n-1)\cdot l}={\omega }_n^{(n-1)\cdot l}$

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:

${𝐃}_n=\left[\begin{array}{cccc}{\omega }_{2n}^0& 0& \dots & 0\\ 0& {\omega }_{2n}^1& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & {\omega }_{2n}^{(n-1)}\end{array}\right]$

Le ultime n righe della sottomatrice di destra coincidono, a meno del segno, con le prime n. Risulta infatti:

${\omega }_{2n}^n={\omega }_{2n}^n\cdot {\omega }_{2n}^0=-{\omega }_{2n}^0$

${\omega }_{2n}^{(n+1)}={\omega }_{2n}^n\cdot {\omega }_{2n}^1=-{\omega }_{2n}^1$

$\dots$

${\omega }_{2n}^{(2n-1)}={\omega }_{2n}^n\cdot {\omega }_{2n}^{(n-1)}=-{\omega }_{2n}^{(n-1)}$

Sulla base delle precedenti considerazioni, si può scrivere:

${𝐅}_{2n}\cdot {𝐏}_{2n}=\left[\begin{array}{ccc}{𝐅}_n& |& {𝐃}_n\cdot {𝐅}_n\\ {𝐅}_n& |& -{𝐃}_n\cdot {𝐅}_n\end{array}\right]=\left[\begin{array}{ccc}{𝐈}_n& |& {𝐃}_n\\ {𝐈}_n& |& -{𝐃}_n\end{array}\right]\left[\begin{array}{ccc}{𝐅}_n& |& 0\\ 0& |& {𝐅}_n\end{array}\right]$

e quindi (${𝐏}_{2n}\cdot {𝐏}_{2n}^T={𝐈}_{2n}$):

${𝐅}_{2n}=\left[\begin{array}{ccc}{𝐈}_n& |& {𝐃}_n\\ {𝐈}_n& |& -{𝐃}_n\end{array}\right]\left[\begin{array}{ccc}{𝐅}_n& |& 0\\ 0& |& {𝐅}_n\end{array}\right]{𝐏}_{2n}^T$

Come esempio di fattorizzazione nel caso $N=4$:

${𝐅}_4=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -i& -1& i\\ 1& -1& 1& -1\\ 1& i& -1& -i\end{array}\right]=\left[\begin{array}{cccc}1& 0& 1& 0\\ 0& 1& 0& -i\\ 1& 0& -1& 0\\ 0& 1& 0& i\end{array}\right]\left[\begin{array}{cccc}1& 1& 0& 0\\ 1& -1& 0& 0\\ 0& 0& 1& 1\\ 0& 0& 1& -1\end{array}\right]\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]$

A seguito della fattorizzazione l'onere computazionale, inizialmente pari a $N^2$, diventa pari a: $2{\left(\frac{N}{2}\right)}^2+\frac{N}{2}$. 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 $D$; il prodotto per la matrice $-D$ si ottiene infatti da quello per $D$ mediante un semplice cambio di segno.

Se l'ordine iniziale è una potenza di due $(N=2^m)$ 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: $N/2\cdot m=(N/2){\log }_{2}N$.

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.

Voci correlate

• Analisi armonica
• Analisi di Fourier
• Trasformata di Fourier
• Trasformata discreta di Fourier
• Trasformata di Fourier veloce

Collegamenti esterni

• Template:Collegamenti esterni
• Template:Cita web