Un esempio di Discrete Cosine Transform

2018-10-29 ( 2018-10-29)

Esercizio di Analisi di Fourier su insiemi finiti:

Consideriamo, per funzioni $2\pi$-periodiche e pari, una approssimazione dell’integrale $\int_{-\pi}^\pi f(x) g(x) dx$, che consideri soltanto un insieme finito di punti equidistribuiti nell’intervallo $[0,2\pi]$: $$ X_N = \left\{ \dfrac{2j\pi}{N} : j=0,\ldots,N-1 \right\} = \{ 0, \frac{2\pi}{N}, \ldots ,\frac{2(N-1)\pi}{N} \}. $$ L’integrale su $X_N$, per $N\to \infty$, è uno dei metodi (trapezi) usati per calcolare approssimazioni numeriche dell’integrale continuo. Supponiamo che $N$ sia pari $N=2n$.

Se indichiamo con $\int_{X_N} f(x) dx$ la somma

$$ \int_ {X_ N} f(x) dx = \frac{1}{N} \sum_{j=0}^{N-1} f(\frac{2j\pi}{N}), $$

si hanno le identità seguenti. Se $0\leq h,k \leq n$ (e quindi si ha che $0\leq h+k\leq 2n = N$, e $-n \leq h-k \leq n$):
$$ \begin{aligned} \int_{X_N} \cos kx \cos hx dx & = \begin{cases} 0 & \text{se $k\neq h$} \\ \frac{1}{2} & \text{se $k=h\not\in { 0 , n }$} \\ 1 & \text{ se $k=h \in {0, n} $.} \end{cases} \ \end{aligned} $$

Si ha infatti che se $0 \lt K \lt N$ (sommando sui complessi) $$ \int_X \cos K x + i \sin K x dx = \int_X e^{iKx} = \frac{1}{N} \sum_{j=0}^{N-1} e^{i K \frac{2 j \pi}{N} } = \frac{1 - e^{i 2 K \pi }}{1 - e^{i 2 K \pi/N}} = 0. $$

Se invece $K \in { 0 , N } $, $$ \int_X \cos K x + i \sin K x dx = 1. $$

Quindi, ricordando che per ogni $h,k,x$ si ha l’identità trigonometrica $$ \begin{aligned} \cos kx \cos hx & = \dfrac{1}{2} [ \cos ( (k+h)x) + \cos( (k-h)x) ], \ k\neq h & \implies 0\lt k+h\lt N ~ & ~ 0 \lt k-h \lt N \ k=h \in {0,n} & \implies k+h \in {0,N} ~& ~
k-h=0 \ k=h \not\in {0,n} & \implies 0\lt k+h \lt N ~& ~ k-h = 0, \ \end{aligned} $$

e quindi le identità di sopra.

Osserviamo che $\cos k x$ è periodica di periodo $2\pi/k$, e quindi $$ x=\frac{2j\pi}{N} \in X_N, ~ k’ = k \mod N \implies \cos k’x = \cos k x,
$$ dato che per ogni $s\in \ZZ$

$ k’ = k + sN \implies \cos k’x = \cos ( (k+sN) \frac{2j\pi}{N} ) = \cos(kx + 2sj \pi) = \cos(kx). $

Analogamente, se $k’=k+n$ si ha, dato che $2n=N$,

$ k’ = k + n \implies \cos k’x = \cos ( (k+n) \frac{2j\pi}{2n} ) = \cos(kx + j \pi) = (-1)^j \cos(kx). $

Questo potrebbe essere un motivo per consideriamo soltanto le armoniche $\cos kx$ con $0\leq k \leq n$.

Ora, dato che la funzione $f(x)$ è pari e $2\pi$-periodica, basta conoscere gli $n+1$ valori $$ f(j \frac{2\pi}{N} ) $$ con $j=0,\ldots,n$, per dedurre i valori di $f$ su tutto $X_N$.

Un insieme equivalente a $X_N$, quasi simmetrico rispetto all’origine, è $ \begin{aligned} S_N & =
{ \frac{2j\pi}{N} : j \in 0, \ldots, n} \cup { \frac{2(j-n)\pi}{N} : j \in 1 , \ldots, n-1 } \\\ & = { \frac{2j\pi}{N} : j \in 0, \ldots, n} \cup { \frac{-2j\pi}{N} : j \in 1 , \ldots, n-1 } \\\ & = { 0, \pm \frac{2\pi}{N},\ldots, \pm \frac{2(n-1)\pi}{N}, \frac{2n\pi}{N} }. \end{aligned} $

Per ogni $f$ periodica di periodo $2\pi$ si ha quindi

$ \int_ {X_ N} f(x) dx = \int_ {S_ N} f(x) = \frac{1}{n} ( \frac{f(0) + f(\pi)}{2} + \sum_ {j=1}^{n-1} f(\frac{j\pi}{n})). $

La decomposizione di Fourier (discreta) di una $f$ pari $2\pi$-periodica potrà quindi scriversi come

$ x\in X_ N: f(x) \sim \frac{a_ 0 + a_ n \cos nx }{2} + \sum_ {k=1}^{n-1} a_ k \cos kx, $

per

$ \begin{aligned} a_ k & = 2 \int_ {X_ N} f(x) \cos k x dx = 2 \int_ {S_ N} f(x) \cos k x dx = \\\ & = \frac{2}{n}( \frac{1}{2}( f(0) + (-1)^k f(\pi)) + \sum_ {j=1}^{n-1} f(\frac{j\pi}{n}) \cos \frac{jk\pi}{n}). \end{aligned} $

Se poniamo infatti

$ \begin{aligned} f(x) & = \sum_ {j=0 }^n \alpha_ j \cos k x, \\\ a_ k & = 2 \int_ {S_ N} f(x) \cos k x dx = \\\ & = 2 \int_ {X_ N} ( \sum_ {j=0}^n \alpha_ j \cos j x \cos k x ) dx = \begin{cases} 2 \alpha_ k, & k \in \{0,n\}; \\\ \alpha_ k, & k \not\in \{0,n\}. \end{cases} \\\ \implies \alpha_ k & = \begin{cases} \frac{a_ k}{2}, & k \in \{0,n\}; \\\ a_ k, & k \not\in \{0,n\}. \end{cases} \end{aligned} $

Osserviamo che questa trasformazione associa ad una funzione $f\from X_S \to \RR$ pari una successione di coefficienti $a_k=0,\ldots n$ (o $\alpha_k$). Ma le funzioni sono determinate dai soli valori $x_j = f(\frac{j\pi}{n}), ~ j=0,\ldots, n$. Si tratta quindi di una trasformazione (lineare e invertibile!) $\RR^{n+1} \to \RR^{n+1}$, molto simile a quella chiamata DCT Discrete Cosine Transform, di importanza fondamentale per alcune applicazioni – {search wikipedia}).

$ (x_ 0,\ldots, x_ j , \ldots, x_ n) \mapsto (a_ 0, \ldots, a_ k, \ldots, a_ n) = \dfrac{2}{n} ( \frac{1}{2}( x_ 0 + (-1)^k x_ n) + \sum_ {j=1}^{n-1} x_ j \cos \frac{jk\pi}{n}) , k=0, \ldots, n. $

L’inversa (presunta) è quella data da $$ (a_ 0,\ldots, a_ k, \ldots, a_ n) \mapsto ( x_ 0, \ldots, x_ j, \ldots, x_ n) = ( \frac{a_ 0 + (-1)^j a_ n }{2} + \sum_ {k=1}^{n-1} a_ k \cos \frac{jk\pi}{n} ), j=0, \ldots, n . $$

Per le funzioni abbiamo dimostrato la convergenza per funzioni regolari a tratti: in questo caso la dimostrazione che è davvero l’inversa può essere un esercizio non difficile di algebra lineare. Vediamo la matrice $4\times 4$ per $n=3$:

$ \frac{2}{3} \begin{bmatrix} \frac{1}{2} & 1 & 1 & \frac{1}{2} \\\ \frac{1}{2} & \cos \frac{\pi}{3} & \cos \frac{2 \pi}{3} & - \frac{1}{2} \\\ \frac{1}{2} & \cos \frac{2 \pi}{3} & \cos \frac{4 \pi}{3} & \frac{1}{2} \\\ \frac{1}{2} & -1 & 1 & - \frac{1}{2} \\\ \end{bmatrix}

\frac{1}{3} \begin{bmatrix} 1 & 2 & 2 & 1 \\\ 1 & 1 & -1 & - 1 \\\ 1 & -1 & -1 & 1 \\\ 1 & -2 & 2 & - 1 \\\ \end{bmatrix}, $

$ \begin{bmatrix} 1 & 2 & 2 & 1 \\\ 1 & 1 & -1 & - 1 \\\ 1 & -1 & -1 & 1 \\\ 1 & -2 & 2 & - 1 \\\ \end{bmatrix} \begin{bmatrix} 1 & 2 & 2 & 1 \\\ 1 & 1 & -1 & - 1 \\\ 1 & -1 & -1 & 1 \\\ 1 & -2 & 2 & - 1 \\\ \end{bmatrix} = \frac{1}{6} \begin{bmatrix} 6 & 0 & 0 & 0 \\\ 0 & 6 & 0 & 0 \\\ 0 & 0 & 6 & 0 \\\ 0 & 0 & 0 & 6 \\\ \end{bmatrix}. $