From Euclidean to Hilbert Spaces

2The Discrete Fourier Transform and its Applications to Signal and Image Processing

The information presented in the previous chapter (Chapter 1) concerning complex inner product spaces and their properties lays the foundations for a very simple introduction to the discrete Fourier transform (DFT).

We simply need to prove that certain functions of complex exponentials constitute an orthogonal basis for a complex inner product space of finite dimension.

From a mathematical standpoint, the DFT is a simple change of basis in a vector space; however, its interpretation is of crucial importance and is extremely useful in the context of applications, notably in signal theory, as we shall see in section 2.6.

This section draws on the excellent work of M. Frazier (2001).

2.1. The space ℓ²(ℤ_N) and its canonical basis

In order to introduce the vector space in which the DFT is to be constructed, we need to make a few adjustments to the notation used thus far.

We shall continue to work with complex vectors with a number of components N, 1 < N < +∞, but a vector in ^N will be considered as a finite sequence.

Our first task is to define ℤ_N.

DEFINITION 2.1.– Two integers i, j ∈ ℤ are said to be congruent modulo N if their difference is divisible by N, that is:

meaning that we can write a = ...