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 of functions
such that
is infinitely differentiable (using limits from the right or from the left at the endpoints) and such that
and
for all
.
is a vector space under the ordinary operations of function addition and scalar multiplication.
Consider the one-dimensional Laplace operator, . 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
.
What are the eigenfunctions (and eigenvalues) of the Laplace operator ? We need to find all the functions
in
such that
for some constant
. Using basic ODE stuff, and using the boundary conditions, it can be shown that the eigenfunctions are
, where
. The corresponding eigenvalues are
. In Fourier analysis, it can be proved that these eigenfunctions do in some sense form a basis of
.
Let . Every function
in
can be associated with a column vector
in
by sampling
at the
points
,
,
,
,
. For each
, let
be the column vector in
obtained by sampling the eigenfunction
at these
points.
It may seem that there are infinitely many vectors here, one for each
. However, there is some redundancy. The vectors
where
,
,
are indeed distinct, but for example
,
, and so on. So we really only have
distinct vectors here, corresponding to
,
,
.
These vectors have some properties that are, in a very nice and very cool way, analogous to certain properties of the eigenfunctions
.
Just as the are eigenfunctions of the Laplace operator, the vectors
are eigenvectors of something called the "discrete Laplace operator", which is a self-adjoint operator, and which arises by approximating
with something called a "second-order centered difference" from numerical analysis. The eigenvalue
corresponding to
is
, which is approximately equal to
when
is much larger than
. 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 {
} is orthogonal, and that the norm of
is
. We can normalize
by dividing it by
and so obtain an orthonormal basis of eigenvectors of the discrete Laplace operator for
.
In ordinary Fourier analysis, we may for example take a function in and write it as an infinite linear combination of the functions
In finite Fourier analysis, we may take a vector in
and write it as a linear combination of the vectors
.