# Welcome.

## January 5, 2011

### Harmonic Analysis Lecture Notes 2

Filed under: 2011 Harmonic Analysis Course — xuhmath @ 6:53 pm

It follows immediately from the previous discussion that

Proposition ${\widehat{f * k} = \hat f \cdot \hat k}$.

Remark This shows that Fourier transform “diagonalizes” convolution.

Returning to ${{\mathbb Z}/ N{\mathbb Z}}$, we saw that

$\displaystyle \hat f (k + N{\mathbb Z}) = \sum_{m=0}^{p-1} e^{-2\pi i k m/N} f(m)$

We can write this in the matrix form (using ${\omega = e^{2\pi i/N}}$),

$\displaystyle \begin{bmatrix} \hat f(0 + N{\mathbb Z}) \\ \hat f (1 + N{\mathbb Z}) \\ \vdots \\ \hat f(N-1 + N{\mathbb Z}) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-(N-1)} \\ 1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2(N-1)} \\ 1 & \omega^{-3} & \omega^{-6} & \cdots & \omega^{-3(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{-(N-1)} & \omega^{-2(N-1)} & \cdots & \omega^{-(N-1)^2} \end{bmatrix} \begin{bmatrix} f(0 + N{\mathbb Z}) \\ f (1 + N{\mathbb Z}) \\ \vdots \\ f(N-1 + N{\mathbb Z}) \end{bmatrix}$

Note that the columns (and rows) are mutually orthogonal vectors of length ${\sqrt{N}}$. Thus the Fourier transform is unitary if we use counting measure to define ${L^2}$ for ${f}$ (i.e., ${G}$) and normalized (i.e., to have total mass ${1}$) counting measure on ${\hat G}$ (to define ${L^2(\hat G)}$); alternatively, we could just redefine the Fourier transform by introducing a factor ${\frac{1}{\sqrt{N}}}$. Generally, for appropriate choice of Haar measure on ${G}$ and ${\hat G}$, we can extend the Fourier transform from ${(L^1 \cap L^2)(G)}$ to a unitary mapping of ${L^2(G)}$ onto ${L^2(G)}$. 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 ${N^2}$ multiplications. However, when ${N}$ is highly composite, we can compute the Fourier transform much more efficiently. Let us just look at the case when ${N}$ is even: denote ${M = \frac{N}{2} -1}$ and reorder the columns (even columns come first, and odd columns come later)

$\displaystyle \begin{bmatrix} \hat f(0 + N{\mathbb Z}) \\ \hat f (1 + N{\mathbb Z}) \\ \vdots \\ \hat f(N-1 + N{\mathbb Z}) \end{bmatrix} = \left[\begin{array}{ccccc|ccccc} 1&1&1&\cdots&1&1 &1&\cdots&1\\ 1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2M} & \omega^{-1} & \omega^{-3} & \cdots &\omega^{-3M} \\ 1 & \omega^{-4} & \omega^{-8} & \cdots & \omega^{-4M} &\omega^{-2} &\omega^{-6} & \cdots & \omega^{-5M}\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots& \vdots & \ddots & \vdots \\ 1 & \omega^{-2M} & \omega^{-4M} & \cdots & \omega^{-M^2} & \omega^{-M} & \omega^{-3M} & \cdots & \omega^{-M(M-1)} \\ \hline 1&1&1&\cdots&1&-1 &-1&\cdots&-1\\ 1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2M} & -\omega^{-1} & -\omega^{-3} & \cdots & -\omega^{-3M} \\ 1 & \omega^{-4} & \omega^{-8} & \cdots & \omega^{-4M} &-\omega^{-2} &-\omega^{-6} & \cdots & -\omega^{-5M}\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots& \vdots & \ddots & \vdots \\ 1 & \omega^{-2M} & \omega^{-4M} & \cdots & \omega^{-M^2} &-\omega^{-M} & -\omega^{-3M} & \cdots & -\omega^{-M(M-1)} \\ \end{array}\right] \begin{bmatrix} f(0 + N{\mathbb Z}) \\ f (2 + N{\mathbb Z}) \\ \vdots \\ f(2M + N{\mathbb Z})\\ f(1 + N{\mathbb Z}) \\ f(3 + N{\mathbb Z}) \\ \vdots \\ f((2M+1) + N{\mathbb Z}) \end{bmatrix},$

where the horizontal and vertical lines each divide the matrix into two equal halves. In view of these quadrants, this says that the ${{\mathbb Z}/ N{\mathbb Z}}$ Fourier transform matrix ${F_N}$ has the form

$\displaystyle F_N = \begin{bmatrix} F_{N/2} &&& \scriptsize \begin{bmatrix} 1 \\ & \omega^{-1} \\ && \omega^{-2} \\ &&& \ddots \\ &&&& \omega^{-M} \end{bmatrix} F_{N/2} \\ & \\ & \\ F_{N/2} &&& \scriptsize \begin{bmatrix} -1 \\ & -\omega^{-1} \\ && - \omega^{-2} \\ &&& \ddots \\ &&&& -\omega^{-M}\end{bmatrix} F_{N/2} \end{bmatrix} \begin{bmatrix} \\ \\ \\ \text{permutation} \\ \\ \\ \\ \end{bmatrix}$

This computation requires ${(N/2)^2 + (N/2)^2 + N = \frac{1}{2} N^2 + N}$ multiplications, which is a modest saving of multiplication a priori. However, if ${N=2^{m}}$, we can iterate this small saving to get the Fast Fourier Transform which takes only ${O(N \log N)}$ many multiplications.