Multidimensional DFT
The ordinary DFT transforms a one-dimensional sequence or array that is a function of exactly one discrete variable n. The multidimensional DFT of a multidimensional array that is a function of d discrete variables for in is defined by:
where as above and the d output indices run from . This is more compactly expressed in vector notation, where we define and as d-dimensional vectors of indices from 0 to, which we define as :
where the division is defined as to be performed element-wise, and the sum denotes the set of nested summations above.
The inverse of the multi-dimensional DFT is, analogous to the one-dimensional case, given by:
As the one-dimensional DFT expresses the input as a superposition of sinusoids, the multidimensional DFT expresses the input as a superposition of plane waves, or multidimensional sinusoids. The direction of oscillation in space is . The amplitudes are . This decomposition is of great importance for everything from digital image processing (two-dimensional) to solving partial differential equations. The solution is broken up into plane waves.
The multidimensional DFT can be computed by the composition of a sequence of one-dimensional DFTs along each dimension. In the two-dimensional case the independent DFTs of the rows (i.e., along ) are computed first to form a new array . Then the independent DFTs of y along the columns (along ) are computed to form the final result . Alternatively the columns can be computed first and then the rows. The order is immaterial because the nested summations above commute.
An algorithm to compute a one-dimensional DFT is thus sufficient to efficiently compute a multidimensional DFT. This approach is known as the row-column algorithm. There are also intrinsically multidimensional FFT algorithms.
Read more about this topic: Discrete Fourier Transform