I was reading a book on image processing by Bernd Jahne and found what he wrote about the Discrete Fourier transform very interesting. The DFT can be computed as {\hat{f} = A f} ({A} has been defined in a previous blog ), so it seems like a linear transformation. A new interpretation is that the rows of {\hat{A}} (or the columns) ({\hat{A}} has been defined in a previous blog ) can be thought of as spanning the vector space of all N-tuples of complex numbers denoted by {\mathbb{C}^N}. First of all, it can be checked that N-tuples of complex numbers form a vector space. On this vector space, an inner product can be defined as follows :

\displaystyle <v,w> = \sum_{k = 0}^{N-1} v_k {\bar{w}_k}

With this definition of inner product on the vector space, one can easily show that, {<\frac{1}{\sqrt{N}}u_i,\frac{1}{\sqrt{N}}u_j> = \delta  (i-j)} where {u_k} is a row (or column) of  {\hat{A}} .

Therefore, if {C \in \mathbb{C}^N} then {C =  \sum_{k = 0}^{N-1} \alpha_k (\frac{1}{\sqrt{N}}u_k)} where {\alpha_k =  <C,\frac{1}{\sqrt{N}}u_k>}. Clearly the {\frac{1}{\sqrt{N}}u_k} span {\mathbb{C}^N}. It can also be checked that {\alpha_k} for {k \in  \{0,1,..,N-1\}} is the 1D Fourier transform. Hence the DFT of a vector {f} is just a projection of {f} on the rows of {\hat{A}}.

In two dimensions, we consider the set of all {M\times  N} complex matrices. This is again a vector space over the field of complex numbers. The basis “vectors” now are the matrices {(B_{u,v})_{m,n} = D_{m,n} =\frac{1}{\sqrt{MN}} exp(\frac{-2\pi  imu}{M}) * exp(\frac{-2\pi inv}{N})} for all {u  \in \{0,1,...,M-1\}, v \in \{0,1,...,N-1\}}. The inner product for two complex matrices is defined as :

\displaystyle <A,B> = \sum_{m=0}^{M-1}\sum_{n=0}^{N-1} A_{m,n} {\bar{B}_{m,n}}

Any complex matrix can then be written as a linear combination of the Basis matrices {B_{u,v}}. {C =  \sum_{u=0}^{M-1}\sum_{v=0}^{N-1} \alpha_{u,v} B_{u,v}}. Then it can be shown that {\alpha_{u,v}} is the 2D Fourier transform for {u \in \{0,1,..,M-1\}, v \in  \{0,1,...,N-1\}}. So, we are projecting {C} onto the Basis vectors {B_{u,v}}. By this reasoning it can be shown that the 2D Fourier transform for a matrix {C} can be written as {A_M C A_N}, where {A_M} is the {M\times M} DFT matrix and {A_N} is the {N \times N} DFT matrix.

NOTE: I was only mentioning {\hat{A}} as I was lazy to write the basis vectors. Hope this did not confuse.

Advertisements