Difference between revisions of "Introduction to Wavelets" - Rhea

Revision as of 17:05, 6 December 2009

==Page Under Construction==

Introduction to Wavelets

Taking Fourier's torch forward...

Background: Why Wavelets?

• I can bet a great deal of money, that as Electrical Engineers, the first person that comes to mind when someone says "SIGNAL PROCESSING" is Fourier.
• Jean Baptiste Joseph Fourier (1768 - 1830) laid a rock-solid foundation for signal analysis, when he claimed that all (continuously differentiable) signals can be represented as the sums of sines and cosines.
• It is hard to imagine the iPod generation without the work this great man did over 2 centuries ago.
• However, the educated world (Electrical Engineers, :D) gradually evolved from their happy continuous perception of life, to the slightly scary, yet extremely promising world of discrete (a.k.a "digital") signals.
• In this world, there is no such thing as continuity (obviously), and signals must be represented as discrete sets of zeros and ones. *These "jumps" would make Fourier very unhappy, because Fourier analysis starts breaking down (leakage, spectrogram uncertainty) when we make abrupt cut-offs and chop signals at will.
• Fundamentally, sines and cosines are infinite length and continuously differentiable, so to represent a jump (zero time or infinite frequency) one would technically need an infinite number of frequencies. Another concept that, albeit well defined on paper, but one that computers detest, is this whole concept of "infinity".

Still, why wavelets?

• This whole concept of breaking a signal down into a summation of simpler or "basis" signals is the cornerstone of Fourier theory.
• However, as mentioned above, the basis sinusoidal signals do not work very well with discontinuities.
• This is where wavelets come in, because they are very good with jumps. (More on this later)
• Another problem we see with Fourier analysis, is the uncomfortable trade-off that exists between time and frequency resolution.
• In other words, if you take a spectrogram of certain data, making your time window finer(increasing temporal resolution), makes your frequency resolution worse. The inverse is also true, i.e. good spectral resolution, causes worse time resolution.
• This is an unhappy decision for signal processors to make, and they often lament, "Why can't I have both?" or "How do I see the tiny variations in frequency while maintaining a reasonably fine resolution in time (and vice versa)"
• Unfortunately, it is impossible using a spectrogram; but wavelets mitigate this problem to a great extent.
• I like how Amara Graps [1] puts it: In wavelet analysis, the scale that we use to look at the data plays a special role; a way of seeing the forest and the trees, so to speak.

Explaining Wavelets

• Now that I've delivered my sales pitch on wavelets, comes the hard part of giving some convincing evidence that they work.
• Having asked even a few grad students, I am convinced that wavelets are a very difficult concept to grasp.
• So before we can use them, let's try to lay a foundation for some of the underlying concepts.

• • Basis Functions

• A basis function can be thought of as a building block for functions.
• Just as a set of unit vectors, (1,0) and (0,1) can represent any vector in 2-D space (Eg: [3,5] = 3[1,0] + 5[0,1]), a set of basis functions can be chosen to represent any function.
• A very important condition for basis functions is that their dot product must be zero; in other words, they must be orthogonal.
• It is intuitive to see different combinations of sines and cosines as the basis functions for a Fourier representation.
• In wavelet analysis, the basis functions are more complicated and called "mother wavelets" or simply wavelets.

• • Time-Frequency Resolution with Wavelets

• We noticed in Fourier Analysis, that with a longer spectrogram window, we get good resolution in the frequency domain, but poor resolution in the time domain. Vice versa for short windows.
• Here is where wavelets are better. The windows in wavelets vary. To isolate the short time changes (temporal resolution) we choose some short basis functions, and some very long basis functions for detailed spectral information.
• The only catch is, we have to choose our basis functions, unlike in Fourier Analysis, where they were all sines and cosines.
• And the problem with choosing them is, wavelets offer an infinite set of such functions.

Applications

• As mentioned before, I am convinced that the theory behind wavelets is complicated, to say the least and beyond the scope of this page.
• I will, however, attempt to present some applications to show that wavelets work!

• But before we explore wavelet analysis, a mathematical background will be useful.

Continuous Time Wavelet Transform

• The continuous time Wavelet Transform is given by:

$ X_w(\tau,s)=\frac{1}{\sqrt{s}} \int_{-\infty}^{\infty} x(t)\psi^{\ast}\left(\frac{t-\tau}{s}\right)\, dt ------(1) $

• Here, the mother wavelet or basis function is given by $ \psi (t) $, and all other analyzing wavelets are derived from translations or scaling of the mother wavelet.

• The parameter $ \tau $ controls the translation of the wavelet, and hence corresponds to the time information in the Wavelet Transform.
• The parameter s, controls the scaling of the wavelet, and hence provides the frequency information in the wavelet transform.
• Also, a close look at the above integral, shows that it is simply a convolution of the mother wavelet and the signal.

Discrete Wavelet Transform

• Now, as many of you might rightly recognize, we may obtain a discrete version of the above transform by simply sampling the time-scale ($ \tau,s $) plane.
• We have to make sure though, as always, that the Nyquist condition is satisfied.
• The resulting series obtained by discretizing the CWT is called the Wavelet Series.
• The computation of the Wavelet Series, while possible may consume significant memory and computation time; and this difficulty lead to the advent of the Discrete Wavelet Transform, similar to the DFT in Fourier Analysis.
• This approach, instead of computing the series for tons of translations and dilations, uses a faster approach: filter banks.

Multi-Resoltion Analysis using Filter Banks

• Wavelet Tree Decomposition (Mallat-tree decomposition) using filter banks is a very useful approach in analyzing signals.
• Consider the block diagram shown above:
• We start by splitting our signal x[n] into it's two constituent frequency bands, i.e., a high-frequency and a low-frequency band.
• If we look at the output of the low pass filter, it is easy to see that the maximum frequency of the signal , say $ \omega $, is now reduced to $ \omega/2 $.
• Therefore, by Nyquist theorem, the sampling rate required to prevent loss of information, is now $ \omega $ instead of $ 2\omega $, required earlier.
• Hence, we can downsample by a factor of 2, safely discarding half the samples of the output image.
• On the other hand, the high pass filtering followed by decimation allows us to isolate high-frequency short-time variations like jumps.
• As, we go further, splitting into more and more levels, the resolution becomes better in both domains.
• The level is usually determined by the length of the signal, as well as it's frequency range.
• So let us see an example of wavelet decomposition.

• We will use a Haar Wavelet in this case, one of the simplest available ones.
• The Haar mother wavelet is given by:

$ \psi(t) = \begin{cases}1 \quad & 0 \leq t < 1/2,\\ -1 & 1/2 \leq t < 1,\\0 &\mbox{otherwise.}\end{cases} $

REFERENCES

• [1] http://www.amara.com/ftpstuff/IEEEwavelet.pdf
• [2] http://www-math.mit.edu/~gs/papers/amsci.pdf