---

SC - Lezione 24 - DFT, Complex Vector Space, Matrix Vector multiplication, IDFT, FFT algorithm

---

Checklist

Checklist

Domande, Keyword e Vocabulary

• Scalar product, orthogonality and basis in complex vector space
• Geometric interpretation of the DFT matrix-vector multiplication
• Projecting from real space into complex space
• Exercise: DFT of the standard base vector of R
• Inverse DFT (synthesis)
• Does the inverse of the matrix exists?
• FFT algorithm

Appunti SC - Lezione 24

Recap of SC - Lezione 23 - Root of Unity, DFT definition, Frequencies, Amplitude Spectrum, DFT as matrix-vector product

For complex matrices, symmetry is defined differently and is referred to as Hermitianity. The conjugate transpose (or Hermitian transpose) of a complex matrix is denoted as .

To compute , you first transpose the matrix, turning the first column into the first row, and so on. Additionally, you must take the complex conjugate of each element.

For real matrices, if , we say the matrix is symmetric. In the case of complex matrices, the elements on the main diagonal must be real numbers, since the complex conjugate of a real number is the number itself. Moreover, for all , the element at position must be the complex conjugate of the element at position .

The matrix that we have seen is not hermitian. Why? Because we don’t have real numbers on the diagonal. But it is symmetric in the real sense.

Conjugate symmetry property:

where the bar denotes the complex conjugation.

When we have computed and shown the amplitude spectrum of a signal we display only the positive ones, one half of the spectrum. The reason is given by this “symmetry” of the matrix .

From the “real part of the DFT matrix of order 256” image, we observed symmetry due to the cosine function, which is inherently symmetric.

In contrast, the phase DFT matrix of order 256 does not exhibit symmetry because it is based on the sine function, which increases in frequency and is not symmetric.

Scalar product, orthogonality and basis in complex vector spaces

One of the two vector must be a column vector.

In the case of complex numbers, there is no commutativity property because:

Which is different from , but they are related since: d satisfies the conjugate symmetry property, so that and (same module).

Two complex vectors and are orthogonal if and only if:

Nothing changes for the 2-norm definiton

The projection of a vector into a vector is given by:

It is worth nothing that if one of the two vectors is a real vector, then the complex scalar product becomes the standard scalar product.

Geometric Interpretation of the DFT

When you multiply the DFT matrix by a vector, it can be interpreted as a sequence of standard scalar products between the first row and the column. This means that you are projecting this vector onto the row.

The interpretation for the DFT is that you project your vector from the real space of dimension into a complex space of dimension , and you are expressing the starting vector again in an orthogonal basis. Because we will see that the rows/columns of the DFT matrix, possess the property that they are orthogonal.

Consider two distints rows of : and The complex scalar product between the two is: , while for the same row is:

When you multiply the DFT matrix by a vector, it can be interpreted as a sequence of standard scalar products between the first row and the column. This means that you are projecting this vector onto the complex space using the DFT matrix . This matrix is orthogonal therefore it is an orthgonal projector, in fact columns and rows of are orthogonal (not orthonormal).

Exercise: DFT of the standard base vectors of R^N

What happens when you apply the DFT to the identity matrix ? You obtain the transformed version of the standard basis vectors of .

At the middle point, you observe the highest frequency. Here, the sine and cosine components are identical, resulting in the maximum frequency. The cosine exhibits the maximum possible oscillations that can be represented on this grid. This middle index is referred to as the Nyquist Point.

Nyquist point Nyquist Frequency

Inverse DFT

Also called synthesis, reconstruct the original time domain from its frequency domain. It’s the inverse operation of the DFT, called Inverse Discrete Fourier Transform

The only things that changes are:

• we don’t have the sign in the exponent of (recall that it represents a complex number that is the root of unity)
• We have to multiply by (normalization)

We can also write this formula using the root of unity definition:

Here in the IDFT formula we have an exponential with positive exponent in contrast with the exponent of the DFT formula that is negative, as we defined it as root of unity with the minus sign:

The difference in sign is essential for the inverse operation of the transform (don’t get confused about this).

Inverse of the DFT matrix

Even the IDFT is a matrix vector multiplication. First thing is to ask if does it exists an inverse? Yes because is not a singular matrix; it is orthogonal so certainly exists an inverse.

The inverse of the matrix is the conjugate transpose divided by :

is the conjugate transpose of the DFT matrix, the generic entry is defined as:

And ofcourse each entry of this matrix is complex number

FFT algorithm

Key Idea of the FFT

The key idea is that we can apply a recursive algorithm, with a complexity of .

Look at this fact:

If i have the root of unity and raise it to 2, it’s simply done by multiplying by 2 the exponent. The square of the 2N-th root of unity is an N-th root of unity.

Squaring doubles the exponent in the exponential expression. The result, matches the definition of . Thus the square of a primite -th root of unity is itself a primitive -th root of unity

Dividing the signal into two DFTs

To compute the DFT of a vector of length 𝑁 by dividing it into two DFTs of length we use the following approach.

We separate the even-indexed and odd-indexed elements, splitting the sum into two parts of length :

• The even-indexed elements are represented as ;
• The odd-indexed elements are represented as ; We recall this fact for explaining why we wrote and in the formula above.

Let and represent the -th elements of the DFT of the even-indexed and odd-indexed parts of , respectively:

Then, we have that:

for

In order to get the second half of , we have to consider the index as the following: we pose so that

Using the property that:

we find that the second half of can be obtained as:

for

Formally:

for

The concatenation of the first part and second part of gives the final result .

• means concatenation of the left vector with the right vector

In summary, the FFT algorithm divides the DFT into smaller DFTs of sizes, typically powers of 2, using the well known Divide-and-Conquer approach. This is done recursively until reaching the base case of the DFT of size 1.

Special factorization of the DFT matrix

This idea of splitting the indexes, can be seen as particular factorization of the matrix into a product of sparser matrices.

Suppose that we start with a and that i take the part with the even index and the part with the odd index, which both have length of and then i put them together.

Where is the identity matrix, is a diagonal matrix: and is the DFT matrix of order 128.

We consider also this:

Then

If is a power of two, the algorithm FFT is good. If N is a prime number then it is a problem.

An example of analysis and synthesis of audio signals

We have this situation in the frequency domain: We then apply a modification of the signal: X_modified(f > 900) = X_modified(f > 900) / 100; it means that the frequencies higher than 900 are “smorzate” and the sound should be changes such that you hear less the higher frequencies.

---