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 ( has been defined in a previous blog ), so it seems like a linear transformation. A new interpretation is that the rows of (or the columns) ( 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 . 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 :
With this definition of inner product on the vector space, one can easily show that, where is a row (or column) of .
Therefore, if then where . Clearly the span . It can also be checked that for is the 1D Fourier transform. Hence the DFT of a vector is just a projection of on the rows of .
In two dimensions, we consider the set of all complex matrices. This is again a vector space over the field of complex numbers. The basis “vectors” now are the matrices for all . The inner product for two complex matrices is defined as :
Any complex matrix can then be written as a linear combination of the Basis matrices . . Then it can be shown that is the 2D Fourier transform for . So, we are projecting onto the Basis vectors . By this reasoning it can be shown that the 2D Fourier transform for a matrix can be written as , where is the DFT matrix and is the DFT matrix.
NOTE: I was only mentioning as I was lazy to write the basis vectors. Hope this did not confuse.