Matrix Form of 2D DFT

Consider the 2-D DFT of an $M\times N$ signal $x[m,n]$ ( $m=0,\cdots,M-1,\;n=0,\cdots,N-1$):

$$X[k,l] = \frac{1}{\sqrt{MN}}\sum_{n=0}^{N-1} \left[ \sum_{m=... ...frac{nl}{N} }, \;\;\;\;\;\;(k=0,\cdots,M-1,\;\;l=0,\cdots,N-1)$$

where we have defined

$$X'[k,n]\stackrel{\triangle}{=}\frac{1}{\sqrt{M}}\sum_{m=0}^{... ...rac{mk}{M}}, \;\;\;\;\;\;\;(k=0,\cdots,M-1,\;\;n=0,\cdots,N-1)$$

where $0 \leq m,k < M,\;\;0 \leq n,l < N$. Note that the dimension of the spectrum $X[k,l]$ is also $M\times N$.

As the summation above is with respect to the row index $m$ while the column index $n$ can be treated as a parameter, this expression can be considered as a one-dimensional Fourier transform of the nth column of the $M\times N$ 2-D signal matrix ${\bf x}=[{\bf x}_0,\cdots,{\bf x}_{N-1}]$, which can be written in column vector (vertical) form as:

$${\bf X'}_n={\bf W}^*_M{\bf x}_n,\;\;\;\;\;\;(n=0,1,\cdots,N-1)$$

where ${\bf W}^*_M$ is a $M\times M$ Fourier transform matrix. Putting all these $N$ columns together, we can write

$${\bf X}'=\left[{\bf X'}_0,\cdots,{\bf X'}_{N-1}\right] ={\... ...bf x}_0,\cdots,{\bf x}_{N-1}\right] = {\bf W}^*_M {\bf x}$$

We also note that the summation in the expression for $X[k,l]$ is with respective to the column index $n$ of ${\bf X}'$ while the row index number $k$ can be treated as a parameter, the expression is one-dimensional Fourier transform of the kth row of ${\bf X}'$, which can be written in row vector (horizontal) form as

$${\bf X}_k^T=({\bf W}^*_N {\bf X'}_k)^T = {\bf X'}_k^T {\bf W}^{*T}_N, = {\bf X'}_k^T {\bf W}^*_N, \;\;\;\;(k=0,\cdots,M-1)$$

where ${\bf W}^{*T}_N={\bf W}^*$ is a $N \times N$ Fourier transform matrix. Putting all these $M$ rows together, we can write

$$\left[ \begin{array}{c} {\bf X}_0^T . . {\bf X}_{N-1... ... . . {\bf X}'_{N-1}^T \end{array} \right] {\bf W}^*_N$$

or more concisely

$${\bf X}={\bf X}'{\bf W}^*_N$$

But since ${\bf X}' ={\bf W}^*_M {\bf x}$, we have

$${\bf X}={\bf W}^*_M {\bf x} {\bf W}^*_N$$

This transform expression indicates that 2D DFT can be implemented by transforming all the rows of ${\bf x}$ and then transforming all the columns of the resulting matrix ${\bf X}'$. The order of the row and column transforms is not important.

Similarly, the inverse 2D DFT can be written as

$${\bf x}= {\bf W}_M {\bf X} {\bf W}_N$$

Again note that ${\bf W}$ is a symmetric unitary matrix:

$${\bf W}^{-1}={\bf W}^{*T}={\bf W}^*$$

It is obvious that the complexity of 2D DFT is $O(N^3)$ which can be reduced to $O(N^2 log_2 N)$ if FFT is used.