Discrete Fourier Transform (general) - Inverse

Inverse

The inverse of the discrete Fourier transform is given as:

where is the multiplicative inverse of in R (if this inverse does not exist, the DFT cannot be inverted).

Proof: Substituting (2) into the right-hand-side of (3), we get

\begin{align} & \frac{1}{n}\sum_{k=0}^{n-1} f_k\alpha^{-jk} \\ & {} = \frac{1}{n}\sum_{k=0}^{n-1}\sum_{j'=0}^{n-1} v_{j'}\alpha^{j'k}\alpha^{-jk} \\ & {} = \frac{1}{n}\sum_{j'=0}^{n-1} v_{j'} \sum_{k=0}^{n-1}\alpha^{(j'-j)k}. \end{align}

This is exactly equal to, because when j'\neq j (by (1) with ), and when . ∎

Read more about this topic:  Discrete Fourier Transform (general)

Famous quotes containing the word inverse:

    “The quality of moral behaviour varies in inverse ratio to the number of human beings involved.”
    —Aldous Huxley (1894–1963)

    “Yet time and space are but inverse measures of the force of the soul. The spirit sports with time.”
    —Ralph Waldo Emerson (1803–1882)