DFT Matrix - Definition

Definition

An N-point DFT is expressed as an N-by-N matrix multiplication as, where is the original input signal, and is the DFT of the signal.

The transformation of size can be defined as, or equivalently:

W = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^{N-1} \\ 1&\omega^2&\omega^4&\omega^6&\cdots&\omega^{2(N-1)}\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^{3(N-1)}\\ \vdots&\vdots&\vdots&\vdots&&\vdots\\ 1&\omega^{N-1}&\omega^{2(N-1)}&\omega^{3(N-1)}&\cdots&\omega^{(N-1)(N-1)}\\ \end{bmatrix},

where is a primitive th root of unity in which . This is the Vandermonde matrix for the roots of unity, up to the normalization factor. Note that the normalization factor in front of the sum and the sign of the exponent in ω 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 choice here makes the resulting DFT matrix unitary, which is convenient in many circumstances.

Fast Fourier Transform algorithms utilize the symmetries of the matrix to reduce the time of multiplying a vector by this matrix, from the usual . Similar techniques can be applied for multiplications by matrices such as Hadamard matrix and the Walsh matrix.

Read more about this topic:  DFT Matrix

Famous quotes containing the word definition:

    “The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
    —William James (1842–1910)

    “It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
    —Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)