Sequence Analysis I: Uniform Series, Cross- and Auto-Correlation, and Fourier Transforms
File last modified 4 October 1996
6.3 Fourier Synthesis and the Fourier Transform
6.3.1 Complete sets of orthonormal functions (basis sets)
There is a fundamental theorem in function theory which says that given a complete set of orthonormal functions, you can construct any other function. This is akin to saying that given enough bricks and mortar, you build just about anything. There is an easy to understand analogy: that of component vectors. Think of a simple two dimensional space (a graph) on which you place an arbitrary vector (from the origin to some point on the graph). You can decompose that vector into two "component" or "basis" vectors that sum up to that vector. For example, consider a vector to x=3, y=4. Then you could make that vector by a combination of two basis vectors of unit length in the x and y directions (i.e., parallel to the x and y axes) with
You can do this for any vector in that two dimensional space (the graph). Pretty simple, huh? In fact, you have to do this implicitly when you give the location of the vector head with a co-ordinate pair. Well the same is true of any arbitrary function, provided that the set of functions you use are orthogonal (just like the x and y unit vectors must be at right angles), and they must be normal (of unit size, just like the unit vectors). This can be expressed for a set of basis functions which we'll call "F" consisting of an infinite series of functions "Fi" such that
where i is not equal to j. The first is simply a statement like two vectors must have a dot product of zero (that is they are at right angles). The functions must have a zero cross-correlation. The second statement is much like the unity length stipulation for a vector. The area under the function must sum to 1.
There are a number of groups of functions which satisfy this relationship, but the one that we are interested in is the sine/cosine series. Yes, they come as a pair. It is convenient to use the transcendental representation of the pair with
where we will interchangeably use the frequency (f) and the angular frequency (omega), where
We know it's annoying to switch back and forth, but sometimes it's easier to use one rather than the other. Assuming you can somehow figure out the coefficients (which correspond to the lengths of the vectors in our two dimensional example), you can then build an arbitrary function out of an infinite sum of these functions:
The original function is "h(t)", is a function of time.
The coefficients we are talking about are the "Hk"
terms, or in the continuum case (the right hand equation) whole
functions (really like a long list of coefficients for a whole
range of frequencies).
6.3.2 An example: building a function from
sines and cosines
Below is an example of an arbitrary function (the green function) which we approximate with fourier series of various lengths. As you can see, the ability to mimic the behavior of the function increases with increasing series length, and the nature of the fit is that the "spikier" elements are fit better by the higher order functions.
6.3.3 The fourier transform and its properties
The equation on the right hand side above is really the definition of a fourier transform. It is equivalent to saying that we can "map" a function that is in the time domain into the frequency domain. This is the exact same thing as saying we can build any function in the time domain as an infinite series of sine/cosine pairs times a function which is really the coefficients of the sines and cosines. That is to say, the H(f) function is really a "rendering" of the h(t) function but in frequency space. Just another way of representing it. How we compute this new representation will be discussed a little next lecture, but suffice it to say that you can think of the pair of representations as fourier transforms of one another, linked by:
where the actual mathematical relationship is
Note the similarity between the two forms. The first goes from frequency to time space (or builds your time varying function out of frequency components) and the second goes from time to frequency space (or computes the components which are stored in H(f) to do the first exercise). The first is called the fourier transform, and the second is called the inverse fourier transform. There, that's it for now. That didn't hurt (much), did it?
6.3.4 Convolution and correlation with
fourier transforms
Why bother with this fourier thing? Well, remember our friend the convolution? If you have two functions "g" and "h" which are
Note that we will follow the tradition that the time-space function will be lower-case, and the frequency space function (it's fourier transform) will be upper case. The properties of the fourier transform are that
or in so many words, the inverse fourier transform of the product
of the fourier transforms is the convolution of the two functions.
So you can convolve two functions by simply taking their transforms,
multiplying them together, and inverse transforming the result.
6.3.5 Signal extraction and filtering
That sounds like the hard way of doing things, doesn't it? Well, what about the signal theory problem where you want to deconvolve your signal to compensate for instrumental response? That is, you have measured a signal "s" which is actually
That is, what you measure is the convolution of your instrumental response function with the original signal. Now with your new-found power (Mr. Fourier, we thank you!), you have
That's right. If you know your response function r(t), which you might obtain from laboratory testing, from theory or from the user's manual, you can take it's fourier transform and divide it into the fourier transform of your observations, then do an inverse transform of the result to get your uncontaminated signal. This is called deconvolution.
Sound too good to be true? Well it sort of is. While the process works in principle, you only know your response function to some limited accuracy, and the ratio S/R tends to be a little unstable because where your response function goes toward zero, the ratio becomes large. Small errors in R will lead to large problems with U. However, with a certain amount of caution, this kind of thing can be (and is routinely) done. In the next lecture, we will talk about a technique for dealing with the noise in your data too.
GoTo Next Lecture
GoTo Lecture TOC
GoTo 12.747 TOC