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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: