DFT matrix

From Wikipedia, the free encyclopedia

The N-point discrete Fourier transform (DFT) can be expressed as a matrix multiplication with an N-by-N matrix, as follows:

X = W x

where x is the original input signal, and X is the DFT of the signal.

The matrix W of size nxn, may be described as a Vandermonde matrix: $W = V (w)$ where w is a vector $w_i = \omega_n^i$ , the nth root of unity.

1 Examples of DFT matrices
2 Unitary transform
3 In the limit: The Fourier operator
4 References
5 External links

[edit] Examples of DFT matrices

[edit] Two-point DFT matrix

The two-point DFT is a simple case, in which the first entry is the DC (sum) and the second entry is the AC (difference).

$\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}/\sqrt{2}$

The first row performs a sum, and the second row performs the difference.

The factor of $1/\sqrt{2}$ is to make the transform unitary (see below).

[edit] Three-point DFT matrix (relationship to S.C.T. or Fortescue transform)

The three-point DFT has a special significance, e.g. as symmetrical components transform (SCT) of Fortescue's 1918 paper, that defines three phase balance, i.e. the 3-DFT breaks a signal up into a DC component, as well as two AC components, one going clockwise, and the other going counter clockwise.

[edit] Four-point DFT matrix

The four-point DFT matrix is as follows:

$\frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 &-i &-1 & i\\ 1 & -1& 1 &-1\\ 1 & i &-1 &-i\end{bmatrix}$

[edit] Eight-point DFT matrix

The first interesting non-trivial integer power of two case is for 8 points:

$W= \frac{1}{\sqrt{8}} \begin{bmatrix} \omega^0 & \omega^0 &\omega^0 & \ldots & \omega^0 \\ \omega^0 & \omega^1 &\omega^2 & \ldots & \omega^7 \\ \omega^0 & \omega^2 &\omega^4 & \ldots & \omega^{14} \\ \omega^0 & \omega^3 &\omega^6 & \ldots & \omega^{21} \\ \omega^0 & \omega^4 &\omega^8 & \ldots & \omega^{28} \\ \omega^0 & \omega^5 &\omega^{10} & \ldots & \omega^{35} \\ \vdots & & \vdots & \ddots & \vdots \\ \omega^0 & \omega^7 &\omega^{14} & \ldots & \omega^{49} \\ \end{bmatrix}$

where

$\omega = e^{-\frac{2 \pi i}{8}} = \frac{1}{\sqrt{2}} - \frac{i}{\sqrt{2}}$

The following image depicts the DFT as a matrix multiply, with elements of the matrix depicted by samples of complex exponentials:

The real part (cosine wave) is denoted by a solid line, and the imaginary part by a dashed (dotted) line.

The top row is all ones (scaled by $1/\sqrt{8}$ for unitarity), so it "measures" the DC component in the input signal. The next row is eight samples of negative one cycle of a complex exponential, i.e. a signal with a fractional frequency of -1/8, so it "measures" how much "strength" there is at fractional frequency +1/8 in the signal. Recall that a matched filter compares the signal with a time reversed version of whatever we're looking for, so when we're looking for fracfreq. 1/8 we compare with fracfreq. −1/8 so that is why this row is a negative frequency. The next row is negative two cycles of a complex exponential, sampled in eight places, so it has a fractional frequency of −1/4, and thus "measures" the extent to which the signal has a fractional frequency of +1/4.

The following summarizes how the 8 point DFT works, row by row, in terms of fractional frequency:

0 measures how much DC is in the signal
−1/8 measures how much of the signal has a fractional frequency of +1/8
−1/4 measures how much of the signal has a fractional frequency of +1/4
−3/8 measures how much of the signal has a fractional frequency of +3/8
−1/2 measures how much of the signal has a fractional frequency of +1/2
−5/8 measures how much of the signal has a fractional frequency of +5/8
−3/4 measures how much of the signal has a fractional frequency of +3/4
−7/8 measures how much of the signal has a fractional frequency of +7/8

Equivalently the last row can be said to have a fractional frequency of +1/8 and thus measure how much of the signal has a fractional frequency of −1/8. In this way, we could say that the top rows of the matrix "measure" positive frequency content in the signal and the bottom rows measure negative frequency component in the signal.

[edit] DFT matrix in general

$W= \frac{1}{\sqrt{N}} \begin{bmatrix} \omega^{0 \cdot 0} & \omega^{0 \cdot 1} & \ldots & \omega^{0 \cdot (n-1)} \\ \omega^{1 \cdot 0} & \omega^{1 \cdot 1} & \ldots & \omega^{1 \cdot (n-1)} \\ \vdots & \vdots & \ddots & \vdots \\ \omega^{(n-1) \cdot 0} & \omega^{(n-1) \cdot 1} & \ldots & \omega^{(n-1) \cdot (n-1)} \\ \end{bmatrix}$

where

$\omega = e^{-\frac{2 \pi i}{N}}$

is the first negative Nth root of unity (i.e. the first root of unity in the direction of negative frequency).

The convention is to go in a negative direction since the DFT is ordinarily thought of as a matched filter, i.e. when looking for a frequency of +1, one correlates the incoming signal with a frequency of −1. Thus each row of the matrix is a sampled complex exponential of negative frequency, that measures the corresponding positive frequency signal strength in the signal under analysis.

Note that the normalization factor in front of the sum ( $1/\sqrt{N}$ ) and the sign of the exponent are merely conventions, and differ in some treatments. All of the following discussion applies regardless of the convention, with at most minor adjustments. The only important thing is that the forward and inverse transforms have opposite-sign exponents, and that the product of their normalization factors be 1/N. However, the $1/\sqrt{N}$ is preferred, since it defines the transform as a unitary transform, and the resulting DFT matrix is a unitary matrix.

[edit] Unitary transform

The DFT is (or can be, through appropriate selection of scaling) a unitary transform, i.e. one that preserves energy. The appropriate choice of scaling is $1/\sqrt{N}$ , so that the energy in the physical domain will be the same as the energy in the Fourier domain, i.e. to satisfy Parseval's theorem.

[edit] In the limit: The Fourier operator

If we make a very large matrix with complex exponentials in the rows (i.e. cosine real parts and sine imaginary parts), and increase the resolution without bound, we approach the kernel of the Fredholm integral equation of the 2nd kind, namely the Fourier operator that defines the continuous Fourier transform. A rectangular portion of this continuous Fourier operator can be displayed as an image, analogous to the DFT matrix, as shown below, where greyscale pixel value denotes numerical quantity: