Finite Fourier Analysis

Motivation

(This is what I currently think of as motivation for finite Fourier analysis. If anyone can improve on this, please do.)

Consider the set $S$ of functions $f:[0,1] \to \mathbb{C}$ such that $f$ is infinitely differentiable (using limits from the right or from the left at the endpoints) and such that $f(0) = f(1)$ and $\frac{d^m f}{dx^m}(0) = \frac{d^m f}{dx^m}(1)$ for all $m \in \mathbb{Z}^+$ . $S$ is a vector space under the ordinary operations of function addition and scalar multiplication.

Consider the one-dimensional Laplace operator, $\frac{d^2}{dx^2}: S \to S$ . Integration by parts shows that this operator is self-adjoint. Therefore, from our experience with the spectral theorem from finite-dimensional linear algebra, we might hope that the eigenfunctions of the Laplace operator in some sense form a basis for $S$ .

What are the eigenfunctions (and eigenvalues) of the Laplace operator $\frac{d^2}{dx^2}:S \to S$ ? We need to find all the functions $f$ in $S$ such that $\frac{d^2f}{dx^2} = \lambda f$ for some constant $\lambda$ . Using basic ODE stuff, and using the boundary conditions, it can be shown that the eigenfunctions are $F_n(x) = e^{i 2 n \pi x}$ , where $n \in \mathbb{Z}$ . The corresponding eigenvalues are $\Lambda_n = -(2 n \pi)^2$ . In Fourier analysis, it can be proved that these eigenfunctions do in some sense form a basis of $S$ .

Let $N \in \mathbb{Z}^+$ . Every function $G$ in $S$ can be associated with a column vector $g$ in $\mathbb{C}^N$ by sampling $G$ at the $N$ points $x=0$ , $x=\frac1N$ , $x=\frac2N$ , $\ldots$ , $x=\frac{N-1}N$ . For each $n \in \mathbb{Z}$ , let $f_n$ be the column vector in $\mathbb{C}^N$ obtained by sampling the eigenfunction $F_n$ at these $N$ points.

It may seem that there are infinitely many vectors $f_n$ here, one for each $n \in \mathbb{Z}$ . However, there is some redundancy. The vectors $f_n$ where $n=0$ , $\ldots$ , $N-1$ are indeed distinct, but for example $f_N=f_0$ , $f_{N+1}=f_1$ , and so on. So we really only have $N$ distinct vectors here, corresponding to $n=0$ , $\ldots$ , $n=N-1$ .

These vectors $f_n$ have some properties that are, in a very nice and very cool way, analogous to certain properties of the eigenfunctions $F_n$ .

Just as the $F_n$ are eigenfunctions of the Laplace operator, the vectors $f_n$ are eigenvectors of something called the "discrete Laplace operator", which is a self-adjoint operator, and which arises by approximating $G''$ with something called a "second-order centered difference" from numerical analysis. The eigenvalue $\lambda_n$ corresponding to $f_n$ is $-4 N^2 \sin^2(\frac{n \pi}N )$ , which is approximately equal to $\Lambda_n$ when $N$ is much larger than $n$ . By directly taking dot products and using the formula for the sum of a finite geometric series, you can prove that the set of eigenvectors { ${f_n : n=0,\ldots, N-1}$ } is orthogonal, and that the norm of $f_n$ is $\sqrt{N}$ . We can normalize $f_n$ by dividing it by $\sqrt{N}$ and so obtain an orthonormal basis of eigenvectors of the discrete Laplace operator for $\mathbb{C}^N$ .

In ordinary Fourier analysis, we may for example take a function in $S$ and write it as an infinite linear combination of the functions $F_n.$ In finite Fourier analysis, we may take a function in $\mathbb{C}^N$ and write it as a linear combination of the functions $f_n$ .

Page

Toolbox

Search

Finite Fourier Analysis

Motivation