It follows immediately from the previous discussion that

**Proposition ** * . *

**Remark ** * This shows that Fourier transform “diagonalizes” convolution. *

Returning to , we saw that

We can write this in the matrix form (using ),

Note that the columns (and rows) are mutually orthogonal vectors of length . Thus the Fourier transform is unitary if we use counting measure to define for (i.e., ) and normalized (i.e., to have total mass ) counting measure on (to define ); alternatively, we could just redefine the Fourier transform by introducing a factor . Generally, for appropriate choice of Haar measure on and , we can extend the Fourier transform from to a unitary mapping of onto . This goes by the name of *Plancherel’s theorem* (cf Lecture 4).

** Foundations of the Fast Fourier Transform (Cooley-Tukey) **

The naïve matrix vector product from above takes multiplications. However, when is highly composite, we can compute the Fourier transform much more efficiently. Let us just look at the case when is even: denote and reorder the columns (even columns come first, and odd columns come later)

where the horizontal and vertical lines each divide the matrix into two equal halves. In view of these quadrants, this says that the Fourier transform matrix has the form

This computation requires multiplications, which is a modest saving of multiplication *a priori*. However, if , we can iterate this small saving to get the Fast Fourier Transform which takes only many multiplications.

### Like this:

Like Loading...

*Related*

## Leave a Reply