Wavelets and Signal Processing

It's true that the Torah -- the visible Torah, that is -- is only one of the possible permutations of the letters of the eternal Torah, as God crated it and delivered it to the angels. By rearranging the letters of the book over the centuries, we may someday arrive again at the original Torah. But the important thing is not the finding, it is the seeking, it is the devotion with which one spins the wheel of the prayer and scripture, discovering the truth little by little.
Diotallevi in Foucault's Pendulum, by Umberto Eco

Using the quote above is, perhaps, ironic, since the character, Diotallevi, in Umberto Eco's Foucault's Pendulum, goes on in the next sentence to denounce the use of computers as tools for seeking truth.

Signal processing and filtering is, in its modest way, an attempt to find a better form for a set of information, either by reshaping it or filtering out selected parts (parts that are sometimes labeled as noise). Put another way, signal processing allows us to uncover a form of the signal that is closer to the truth (or a truth).

Although we have powerful computing and mathematical tools, perhaps there is some value in taking Diotellevi warning to heart: your machine may bring you delirium instead of ecstasy. Inexpensive high speed computing, modern statistics and mathematics sometimes seem like the modern version of rune marked bones, thrown by a shaman in cave lit by a smoky tallow lamp. It remains to be seen whether computing and mathematics are more reliable than the bones at unmasking truth and predicting the future. In theory statistics give us tools that tell us how successful our techniques are. But statistical tests rarely give us a final answer.

Wavelets

Preface

The grains of understanding that I have gathered regarding wavelets has come from reading several books and a number of journal articles. The wavelet web pages published here cannot replace this literature. In fact, what is written here is largely incomplete without this literature. My point of view differs from most authors who write on wavelets. I am not a mathematician. I am a software engineer and my interests in wavelets comes from an applied point of view. A software engineer wants to know what the algorithms is. Most software engineers are only interested in proofs only when computer simulation cannot show that the algorithm is robust and reliable (the algoritm cannot be tested through a complete range of values). As I understand the mathematicians view, they are interested in proof, because that is the nature of mathematics.

In most cases when a topic is discussed, I have published the Java or C++ code. This code is documented with either Javadoc or doxygen formatted comments and I have tried to include extensive documentation. Working software is missing from much of the wavelet literature, so I hope that this is a useful contribution. I hope that the material published here will make your journey easier and faster than mine has been.

These web pages evolved over a couple of years. This was entirely unplanned. I never expected that I would spend so much time on a topic which previously seemed alien to my background. As I've noted in the discussion of Haar wavelets, I stumbled into wavelets by accident. Wavelets lead me to classical signal processing (e.g., signal processing based on the Fourier transform), since this provides the foundation for signal processing using the wavelet transform. As I read more of the literature on wavelets, I found a wide breadth of applications for wavelets. I also found interconnections between wavelets other areas like fractal mathematics. As I found more interconnections between wavelets and other areas, I found it difficult to disentangle myself from this fascinating web of ideas.

The nature of my discovery and fascination has followed a wandering course, which is reflected in the structure of these web pages. As I read the literature on wavelets, finance, statistics, fractals and other areas, I wrote the web pages that are cataloged here, as a reference for myself and for others.

I originally became interested in wavelets because I had some fuzzy idea that the wavelet transform might have some application in quantitative finance. My early web pages explore simple Haar wavelets and an even more simplistic (and in some cases misguided) application of Haar wavelet based filters to financial time series. The later web pages were written as I came to understand other wavelet functions through the lens of the "lifting scheme". As time has gone on I have concentrated more on applications, since I now have a number of wavelet tool hanging on my "peg board". The web page on time series forecasting is built on a broad foundation which includes a collection of wavelet functions, wavelet packets, lossless wavelet compression, histograms, statistical functions, Gaussian distributed random numbers and some fractal mathematics (the Hurst exponent). The background for this web page also include my modest sampling of the literature on quantitative finance and economics.

References

One of the things that is missing so far is a centralized annotated bibliography. This is a side effect of the evolutionary nature of these web pages. Rather than having a single bibliography, the references to literature (books, articles and web pages) are scattered among the web pages. Many of the basic references can be found on the web page that discusses the applicaton of the the Haar transform to time series information.

What can wavelets be used for?

Fourier analysis, using the Fourier transform, is a powerful tool for analyzing the components of a stationary signal (a stationary signal is a signal that repeats). For example, the Fourier transform is a powerful tool for processing signals that are composed of some combination of sine and cosine signals.

The Fourier transform is less useful in analyzing non-stationary data, where there is no repetition within the region sampled. Wavelet transforms (of which there are, at least formally, an infinite number) allow the components of a non-stationary signal to be analyzed. Wavelets also allow filters to be constructed for stationary and non-stationary signals.

Although Haar wavelets date back to the beginning of the twentieth century, wavelets as they are thought of today are new. Wavelet mathematics is less than a quarter of a century old. Some techniques, like the wavelet packet transform are barely ten years old. This makes wavelet mathematics a new tool which is slowly moving from the realm of mathematics into engineering. For example, the JPEG 2000 standard is based on the wavelet lifting scheme.

The Fourier transform shows up in a remarkable number of areas outside of classic signal processing. Even taking this into account, I think that it is safe to say that the mathematics of wavelets is much larger than that of the Fourier transform. In fact, the mathematics of wavelets encompasses the Fourier transform. The size of wavelet theory is matched by the size of the application area. Initial wavelet applications involved signal processing and filtering. However, wavelets have been applied in many other areas including non-linear regression and compression. An offshoot of wavelet compression allows the amount of determinism in a time series to be estimated.

Rules for wavelets

All of the wavelet algorithms that I am aware of must be applied to a data set (a time series or a signal) that with a power of two number of elements (e.g., 256 elements = 28).

All of the algorithms discussed on these web pages are ordered wavelet transforms. This means that the result consists of a wavelet scaling function value (also known as a smooth value or a low pass filter value), followed by bands of wavelet function values (sometimes called wavelet coefficients), in increasing frequency. The sizes of these wavelet coefficient bands are ordered in increasing powers of two. If there are N elements in the data set (where N is a power of two) The coefficient bands following the scaling value will have sizes 20, 21, 22 ... N/2.

The wavelet coefficient bands represent change in the signal at a paticular resolution.

Wavelets: Table of Contents


Signal Processing

Acknowledgments

I strongly believe that it is important to acknowledge and thank those who help an author in their path between an idea and a published work. In working on wavelets and, to a lesser extent, Fourier analysis, I have had many helpful discussions with colleagues.

I would like to thank Chris Strom for his encouragement and his generosity with his time.

Over time I hope to have the opportunity to add to the list above. For right now I don't feel free to thank all of my colleagues by name. I still hope that if any of these individuals make their way here, they will accept my warmest thanks. It was a great pleasure working with you and I appreciate your patience with my questions and half baked ideas.

I am the sole author of these web pages and they have not been written in direct consultation with anyone. Any errors are mine.




Ian Kaplan, 2001, 2002, 2003