Editing Discrete Fourier transform (section)

==Multidimensional DFT==<!-- This section is linked from [[Fast Fourier transform]] -->
The ordinary DFT transforms a one-dimensional sequence or [[matrix (mathematics)|array]] <math>x_n</math> that is a function of exactly one discrete variable ''n''.  The multidimensional DFT of a multidimensional array <math>x_{n_1, n_2, \dots, n_d}</math> that is a function of ''d'' discrete variables <math>n_\ell = 0, 1, \dots, N_\ell-1</math> for <math>\ell</math> in <math>1, 2, \dots, d</math> is defined by:

:<math>X_{k_1, k_2, \dots, k_d} = \sum_{n_1=0}^{N_1-1} \left(\omega_{N_1}^{~k_1 n_1} \sum_{n_2=0}^{N_2-1} \left( \omega_{N_2}^{~k_2 n_2} \cdots \sum_{n_d=0}^{N_d-1} \omega_{N_d}^{~k_d n_d}\cdot x_{n_1, n_2, \dots, n_d} \right) \right) , </math>

where <math>\omega_{N_\ell} = \exp(-i 2\pi/N_\ell)</math> as above and the ''d'' output indices run from <math>k_\ell = 0, 1, \dots, N_\ell-1</math>.  This is more compactly expressed in [[coordinate vector|vector]] notation, where we define <math>\mathbf{n} = (n_1, n_2, \dots, n_d)</math> and <math>\mathbf{k} = (k_1, k_2, \dots, k_d)</math> as ''d''-dimensional vectors of indices from 0 to <math>\mathbf{N} - 1</math>, which we define as <math>\mathbf{N} - 1 = (N_1 - 1, N_2 - 1, \dots, N_d - 1)</math>:

:<math>X_\mathbf{k} = \sum_{\mathbf{n}=\mathbf{0}}^{\mathbf{N}-1} e^{-i 2\pi \mathbf{k} \cdot (\mathbf{n} / \mathbf{N})} x_\mathbf{n} \, ,</math>

where the division <math>\mathbf{n} / \mathbf{N}</math> is defined as <math>\mathbf{n} / \mathbf{N} = (n_1/N_1, \dots, n_d/N_d)</math> 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:

:<math>x_\mathbf{n} = \frac{1}{\prod_{\ell=1}^d N_\ell} \sum_{\mathbf{k}=\mathbf{0}}^{\mathbf{N}-1} e^{i 2\pi \mathbf{n} \cdot (\mathbf{k} / \mathbf{N})} X_\mathbf{k} \, .</math>

As the one-dimensional DFT expresses the input <math>x_n</math> as a superposition of sinusoids, the multidimensional DFT expresses the input as a superposition of [[plane wave]]s, or multidimensional sinusoids. The direction of oscillation in space is <math>\mathbf{k} / \mathbf{N}</math>. The amplitudes  are <math>X_\mathbf{k}</math>.  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 [[function composition|composition]] of a sequence of one-dimensional DFTs along each dimension.  In the two-dimensional case <math>x_{n_1,n_2}</math> the <math>N_1</math> independent DFTs of the rows (i.e., along <math>n_2</math>) are computed first to form a new array <math>y_{n_1,k_2}</math>. Then the <math>N_2</math> independent DFTs of ''y'' along the columns (along <math>n_1</math>) are computed to form the final result <math>X_{k_1,k_2}</math>.  Alternatively the columns can be computed first and then the rows. The order is immaterial because the nested summations above [[commutative operation|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 [[Fast Fourier transform#Multidimensional FFTs|multidimensional FFT algorithms]].

=== The real-input multidimensional DFT ===
For input data <math>x_{n_1, n_2, \dots, n_d}</math> consisting of [[real numbers]], the DFT outputs have a conjugate symmetry similar to the one-dimensional case above:

:<math>X_{k_1, k_2, \dots, k_d} = X_{N_1 - k_1, N_2 - k_2, \dots, N_d - k_d}^* ,</math>

where the star again denotes complex conjugation and the <math>\ell</math>-th subscript is again interpreted modulo <math>N_\ell</math> (for <math>\ell = 1,2,\ldots,d</math>).