Search for probability and statistics terms on Statlect
StatLect

Discrete Fourier transform

by , PhD

The Discrete Fourier Transform (DFT) is a linear operator used to perform a particularly useful change of basis.

It transforms a vector into a set of coordinates with respect to a basis whose vectors have two important characteristics:

  1. they are orthogonal;

  2. their entries are samples of the same periodic function taken at different frequencies.

Table of Contents

Definition

Here is a definition.

Definition Let x be an $N	imes 1$ vector. The discrete Fourier transform of x is an $N	imes 1$ vector X whose entries satisfy[eq1]where i is the imaginary unit.

Periodicity

Remember that[eq2]

Since the sine and the cosine are periodic functions with period $2pi $, the function [eq3]is a periodic function of $j$ with period[eq4]

Plot of the periodic functions used in the Discrete Fourier Transform.

Inverse transform

The DFT is easily invertible.

Proposition Let x and X be an $N	imes 1$ vector and its discrete Fourier transform respectively. Then,[eq5]

Proof

We can write[eq6]If $j=l$, then[eq7]If $j
eq l$, we can use the geometric series formula[eq8]to write[eq9]where in step $rame{A}$ we use the fact that [eq10] is a function of $left( j-l
ight) $ that has period 1. By putting together the equations above, we get[eq11]

Fourier matrix

We can use a matrix to gather the values of the periodic functions used in the discrete Fourier transform.

Define[eq12]so that[eq13]

Then, we can define the $N	imes N$ Fourier matrix[eq14]

We can use F to write the DFT in matrix form[eq15]

By using the definition of matrix multiplication, you can easily check that this equation is equivalent to the equations we have used above to define the DFT.

The equation makes clear that the DFT is a linear operator with matrix F.

Note that F is a symmetric matrix.

Inverse Fourier matrix

The inverse transform can be written as[eq16]

The entries of the inverse Fourier matrix $F^{-1}$ have already been derived above:[eq17]

Frequency-domain representation

Denote by [eq18] the the k-th column of $F^{-1}$.

Remember that post-multiplying a matrix by a column vector is the same as taking a linear combination of the columns of the matrix.

Therefore, we can write the inverse transform as[eq19]

This is called frequency-domain representation of x.

In other words, x can be written as a linear combination of (samples of) periodic functions [eq18] that have different frequencies.

The coefficients of the linear combination are [eq21].

Orthogonality

The columns of the Fourier matrix and of its inverse are orthogonal to each other.

Proof

Consider two columns of the Fourier matrix $F_{ullet ,j}$ and $F_{ullet ,l}$, with $j
eq l$. Their inner product is [eq22]where $st $ denotes conjugate transposition. The fact that the sum in the penultimate line is equal to zero was proved previously (see the the formula for the inverse transform). We leave as an exercise (see below) the proof that the columns of the inverse Fourier matrix are orthogonal.

However, the Fourier matrix, as defined above, is not unitary because its columns do not have unit norm.

Actually, all the columns have norm equal to $sqrt{N}$.

Proof

Consider a column of the Fourier matrix $F_{ullet ,j}$. Its norm is: [eq23]

To make the Fourier matrix unitary some authors define the Discrete Fourier Transform as[eq24]in which case the inverse transform is[eq25]

This is sometimes called the Unitary DFT.

The Fourier matrix of the Unitary DFT is [eq26]

Its inverse is[eq27]where $st $ denotes conjugate transposition.

Learn more about the DFT

More details about the DFT can be found in the following lectures:

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Prove that the columns of the inverse Fourier matrix are orthogonal to each other.

Solution

Consider two columns of the inverse Fourier matrix [eq28] and [eq29], with $j
eq l$. Their inner product is [eq30]

How to cite

Please cite as:

Taboga, Marco (2021). "Discrete Fourier transform", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/discrete-Fourier-transform.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.