The discrete Fourier transform (DFT) is an invertible linear mapping defined by:
, where , and
The unitary discrete Fourier transform is given by multiplying with .
The unitary DFT has the convenient property of preserving 2-norms. The inverse of the DFT is given by :
, where , and
The DFT can be viewed as a change of basis from the standard basis to a complex exponential basis. The DFT is interesting because, in this new basis, the coefficients correspond to the weights of sinusoids at different frequencies. Thus, effectively the DFT decomposes the vector components into a linear combination of sinusoids, with the weights given by the coefficients. This in turn allows for a powerful way to modify signals by attenuating or amplifying the desired sinusoids.
The DFT generalizes easily to a multi-dimensional setting. Here the vectors are multi-dimensional arrays, and the exponential basis functions are radially extended from the 1-dimensional case. This transformation is separable: it can be computed by performing 1-dimensional DFT:s for each column in each dimension successively. For example, a 2-dimensional DFT is performed by doing 1-dimensional DFTs first on rows, and then on columns (or the other way around).
Pastel implements efficient algorithms for computing the DFT and the IDFT, when is a power of two. Both the standard and the orthogonal version are provided.