Applying the Haar Wavelet Transform to Time Series Information

Contents
Introduction
What a long, strange trips its been
The wavelet technique for analyzing a signal or time series
The Language of Wavelets
Applying Wavelets and Java Source Code
Financial Time Series
Why Haar Wavelets?
Haar Wavelets
Filtering Spectrum
Noise Filters
Wavelets vs. Simple Filters
Limitations of the Haar Wavelet Transform
Wavelets and Parallelism
Java Source Code Download
Resources
References, Books
References, Web published


Links to sub-pages
Daubechies Wavelets
Filtering Using Haar Wavelets
The Haar Wavelet Transform and Noise Filters
Wavelet Noise Thresholding
Wavelets vs. Simple Filters
Wavelets in Java (includes histogramming and simple statistical algorithms)

Introduction

This was the first web page I wrote on Wavelets. From this seed grew other web pages which discuss a variety of wavelet related topics. For a "table of contents" see Wavelets and Signal Processing. This web page applies the wavelet transform to a time series composed of stock market close prices. Later web pages expand on this work in a variety of areas (e.g., compression, spectral analysis and forecasting).

When I started out I thought that I would implement the Haar wavelet and that some of my colleagues might find it useful. I did not expect signal processing to be such an interesting topic. Nor did I understand who many different areas of computer science, mathematics, and quantitative finance would be touched by wavelets. I kept finding that "one thing lead to another", making it difficult to find a logical stopping place. This wandering path of discovery on my part also accounts for the somewhat organic growth of these web pages. I have tried to tame this growth and organize it, but I fear that it still reflects the fact that I did not know where I was going when I started.

The Java code published along with this web page reflect the first work I did on wavelets. More sophisticated, lifting scheme based, algorithms, implemented in Java can be found on other web pages. The wavelet lifting scheme code, published on other web pages, is simpler and easier to understand. The wavelet lifting scheme also provides an elegant and powerful framework for implementing a range of wavelet algorithms.

In implementing wavelet packet algorithms, I switched from Java to C++. The wavelet packet algorithm I used is simpler and more elegant using C++'s operator overloading features. C++ also supports generic data structures (templates), which allowed me to implement a generic class hierarchy for wavelets. This code includes several different wavelet algoriths, including Haar, linear interpolation and Daubechies D4.

Like the wavelet algorithms, the financial modeling done here represents very early work. When I started working on these web pages I had no experience with modeling financial time series. The work described on this web page lead to more intensive experiments with wavelet filters in financial models, which I continue to work on. On this web page I use stock market close prices. In financial modeling one usually uses returns, since what you are trying to predict is future return.

I became interested in wavelets by accident. I was working on software involved with financial time series (e.g., equity open and close price), so I suppose that it was an accident waiting to happen. I was reading the February 2001 issue of WIRED magazine when I saw the graph included below. Every month WIRED runs various graphic visualizations of financial data and this was one of them.

If stock prices do indeed factor in all knowable information, a composite price graph should proceed in an orderly fashon, as new information nudges perceived value against the pull of established tendencies. Wavelet analysis, widely used in communications to separate signal (patterned motion) from noise (random activity), suggests otherwise.

This image shows the results of running a Haar transform - the fundamental wavelet formula -- on the daily close of the Dow and NASDQ since 1993. The blue mountains constitute signal. The embedded red spikes represent noise, of which the yellow line follows a 50-day moving average.

Noise, which can be regarded as investor ignorance, has risen along with the value of both indices. But while noise in the Dow has grown 500 percent on average, NASDAQ noise has ballooned 3,000 percent, far outstripping NASDAQ's spectacular 500-percent growth during the same period. Most of this increase has occurred since 1997, with an extraordinary surge since January 2000. Perhaps there was a Y2K glich after all -- one that derailed not operating systems and CPUs, but --> -- investor psychology. - Clem Chambers (clemc@advfn.com).

Graph and quote from WIRED Magazine, February 2001, page 176

I am a Platonist. I believe that, in the abstract, there is truth, but that we can never actually reach it. We can only reach an approximation, or a shadow of truth. Modern science expresses this as Heisenberg uncertainty.

A Platonist view of a financial time series is that there is a "true" time series that is obscured to some extent by noise. For example, a close price or bid/ask time series for a stock moves on the basis of the supply and demand for shares. In the case of a bid/ask time series, the supply/demand curve will be surrounded by the noise created by random order arrival. If, somehow, the noise could be filtered out, we would see the "true" supply/demand curve. Software which uses this information might be able to do a better job because it would not be confused by false movements created by noise.

The WIRED graph above suggests that wavelet analysis can be used to filter a financial time series to remove the associated noise. Of course there is a vast area that is not addressed by the WIRED quote. What, for example, constitutes noise? What are wavelets and Haar wavelets? Why are wavelets useful in analyzing financial time series? When I saw this graph I knew answers to none of these questions.

The analysis provided in the brief WIRED paragraph is shallow as well. Noise in the time series increases with trading volume. In order to claim that noise has increased, the noise should be normalized for trading volume.

What a long, strange trip its been

Reading is a dangerous thing. It can launch you off into strange directions. I moved from California to Santa Fe, New Mexico because I read a book. That one graph in WIRED magazine launched me down a path that I spent many months following. Like any adventure, I'm not sure if I would have embarked on this one if I had known how long and, at times, difficult, the journey would be.

Years ago, when it first came out, I bought a copy of the book The World According to Wavelets by Barbara Hubbard, on the basis of a review I read in the magazine Science. The book sat on my shelf unread until I saw the WIRED graph.

Wavelets have been somewhat of a fad, a buzzword that people have thrown around. Barbara Hubbard started writing The World According to Wavelets when the wavelet fad was starting to catch fire. She provides an interesting history of how wavelets developed in the mathematical and engineering worlds. She also makes a valiant attempt to provide an explanation of what the wavelet technique is. Ms. Hubbard is a science writer, not a mathematician, but she mastered a fair amount of basic calculus and signal processing theory (which I admire her for). When she wrote The World According to Wavelets there were few books on wavelets and no introductory material. Although I admire Barbara Hubbard's heroic effort, I had only a surface understanding of wavelets after reading The World According to Wavelets.

There is a vast literature on wavelets and their applications. From the point of view of a software engineer (with only a year of college calculus), the problem with the wavelet literature is that it has largely been written by mathematicians, either for other mathematicians or for students in mathematics. I'm not a member of either group, so perhaps my problem is that I don't have a fluent grasp of the language of mathematics. I certianly feel this when ever I read journal articles on wavelets. However, I have tried to concentrate on books and articles that are explicitly introductory and tutorial. Even these have proven to be difficult.

The first chapter of the book Wavelets Made Easy by Yves Nievergelt starts out with an explaination of Haar wavelets (these are the wavelets used to generate the graph published in WIRED). This chapter has numerous examples and I was able to understand and implement Haar wavelets from this material (links to my Java code for Haar wavelets can be found below). A later chapter discusses the Daubechies wavelet transform. Unfortunately, this chapter of Wavelets Made Easy does not seem to be as good as the material on Haar wavelets. There appear to be a number of errors in this chapter and implementing the algorithm described by Nievergelt does not result in a correct wavelet transform. Among other things, the wavelet coefficients for the Daubechies wavelets seem to be wrong. My web page on the Daubechies wavelet transform can be found here. The book Ripples in Mathematics (see the references at the end of the web page) is a better reference.

The wavelet technique for analyzing a signal or time series

There is a vast literature on wavelets. This includes thousands of journal articles and many books. The books on wavelets range from relatively introductory works like Nievergelt's Wavelets Made Easy (which is still not light reading) to books that are accessable only to graduate students in mathematics. There is also a great deal of wavelet material on the Web. This includes a number of tutorials (see Web based reference, below).

Given the vast literature on wavelets, there is no need for yet another tutorial. But it might be worth while to summarize my view of wavelets as they are applied to 1-D signals or time series (an image is 2-D data). A time series is simply a sample of a signal or a record of something, like temperature, water level or market data (like equity close price).

Wavelets allow a time series to be viewed in multiple resolutions. Each resolution reflects a different frequency. The wavelet technique takes averages and differences of a signal, breaking the signal down into spectrum. All the wavelet algorithms that I'm familiar with work on time series a power of two values (e.g., 64, 128, 256...). Each step of the wavelet transform produces two sets of values: a set of averages and a set of differences (the differences are referred to as wavelet coefficients). Each step produces a set of averages and coefficients that is half the size of the input data. For example, if the time series contains 256 elements, the first step will produce 128 averages and 128 coefficients. The averages then become the input for the next step (e.g., 128 averages resulting in a new set of 64 averages and 64 coefficients). This continues until one average and one coefficient (e.g., 20) is calculated.

The average and difference of the time series is made across a window of values. Most wavelet algorithms calculate each new average and difference by shifting this window over the input data. For example, if the input time series contains 256 values, the window will be shifted by two elements, 128 times, in calculating the averages and differences. The next step of the calculation uses the previous set of averages, also shifting the window by two elements. This has the effect of averaging across a four element window. Logically, the window increases by a factor of two each time.

In the wavelet literature this tree structured recursive algorithm is referred to as a pyramidal algorithm.

The power of two coefficient (difference) spectrum generated by a wavelet calculation reflect change in the time series at various resolutions. The first coefficient band generated reflects the highest frequency changes. Each later band reflects changes at lower and lower frequencies.

There are an infinite number of wavelet basis functions. The more complex functions (like the Daubechies wavelets) produce overlapping averages and differences that provide a better average than the Haar wavelet at lower resolutions. However, these algorithms are more complicated.

The Language of Wavelets

Every field of specialty develops its own sub-language. This is certainly true of wavelets. I've listed a few definitions here which, if I had understood their meaning would have helped me in my wanderings through the wavelet literature.

Applying Wavelets and Java Source Code

These Web pages publish some heavily documented Java source code for the Haar wavelet transform. Books like Wavelets Made Easy explain some of the mathematics behind the wavelet transform. I have found, however, that the implemation of this code can be at least as difficult as understanding the wavelet equations. For example, the in-place Haar wavelet transform produces wavelet coefficients in a butterfly pattern in the original data array. The Java source published here includes code to reorder the butterfly into coefficient spectrums which are more useful when it comes to analyzing the data. Although this code is not large, it took me most of a Saturday to implement the code to reorder the butterfly data pattern.

The wavelet Lifting Scheme, developed by Wim Sweldens and others provides a simpler way to look as many wavelet algorithms. I started to work on Lifting Scheme wavelet implementations after I had written this web page and developed the software. The Haar wavelet code is much simpler when expressed in the lifting scheme. See my web page The Wavelet Lifting Scheme.

The link to the Java source download Web page is below.

Financial Time Series

There are a variety of wavelet analysis algorithms. Different wavelet algorithms are appplied depending on the nature of the data analyzed. The Haar wavelet, which is used here is very fast and works well for the financial time series (e.g., the close price for a stock). Financial time series are non-stationary (to use a signal processing term). This means that even within a window, financial time series cannot be described well by a combination of sin and cos terms. Nor are financial time series cyclical in a predictable fashion (unless you believe in Elliot waves). Financial time series lend themselves to Haar wavelet analysis since graphs of financial time series tend to jagged, without a lot of smooth detail. For example, the graph below shows the daily close price for Applied Materials over a period of about two years.

Daily close price for Applied Materials (symbol: AMAT), 12/18/97 to 12/30/99.

The Haar wavelet algorithms I have implemented work on data that consists of samples that are a power of two. In this case there are 512 samples.

Why Haar Wavelets?

There are a wide variety of popular wavelet algorithms, including Daubechies wavelets, Mexican Hat wavelets and Morlet wavelets. These wavelet algorithms have the advantage of better resolution for smoothly changing time series. But they have the disadvantage of being more expensive to calculate than the Haar wavelets. The higer resolution provided by these wavlets is not worth the cost for financial time series, which are characterized by jagged transitions.

Haar Wavelets

The Haar wavelet algorithms published here are applied to time series where the number of samples is a power of two (e.g., 2, 4, 8, 16, 32, 64...) The Haar wavelet uses a rectangular window to sample the time series. The first pass over the time series uses a window width of two. The window width is doubled at each step until the window encompasses the entire time series.

Each pass over the time series generates a new time series and a set of coefficients. The new time series is the average of the previous time series over the sampling window. The coefficients represent the average change in the sample window. For example, if we have a time series consisting of the values v0, v1, ... vn, a new time series, with half as many points is calculated by averaging the points in the window. If it is the first pass over the time series, the window width will be two, so two points will be averaged:

   for (i = 0; i < n; i = i + 2)
     si = (vi + vi+1)/2;

The 3-D surface below graphs nine wavelet spectrums generated from the 512 point AMAT close price time series. The x-axis shows the sample number, the y-axis shows the average value at that point and the z-axis shows log2 of the window width.

The wavelet coefficients are calcalculated along with the new average time series values. The coefficients represent the average change over the window. If the windows width is two this would be:

   for (i = 0; i < n; i = i + 2)
     ci = (vi - vi+1)/2;

The graph below shows the coefficient spectrums. As before the z-axis represents the log2 of the window width. The y-axis represents the time series change over the window width. Somewhat counter intutitively, the negative values mean that the time series is moving upward

 vi is less than vi+1 
      so
 vi - vi+1 will be less than zero
Positive values mean the the time series is going down, since vi is greater than vi+1. Note that the high frequency coefficient spectrum (log2(windowWidth) = 1) reflects the noisiest part of the time series. Here the change between values fluctuates around zero.

Plot of the Haar coefficient spectrum. The surface plots the highest frequency spectrum in the front and the lowest frequency spectrum in the back. Note that the highest frequency spectrum contains most of the noise.

Filtering Spectrum

The wavelet transform allows some or all of a given spectrum to be removed by setting the coefficients to zero. The signal can then be rebuilt using the inverse wavelet transform. Plots of the AMAT close price time series with various spectrum filtered out are shown here.

Noise Filters

Each spectrum that makes up a time series can be examined independently. A noise filter can be applied to each spectrum removing the coefficients that are classified as noise by setting the coefficients to zero.

This web page shows a histogram analysis of the three highest frequency spectrum of the AMAT close price. The result of a filter that removes the points that fall within a gaussian curve in each spectrum is also shown. The gaussian curve has a mean and standard deviation of the coefficients in that spectrum.

Another way to remove noise is to use thresholding. My web page outlining one thresholding algorithm can be found here.

Wavelets vs. Simple Filters

How do Haar wavelet filters compare to simple filters, like windowed mean and median filters? A plot of the AMAT time series, filtered with a median filter (which in this case is virtually identical to a mean filter) is shown here here. These filters can be compared to the spectrum filters (where a given wavelet coefficient spectrum is filered out) here..

Whether a wavelet filter is better than a windowed mean filter depends on the application. The wavelet filter allows specific parts of the spectrum to be filtered. For example, the entire high frequency spectrum can be removed. Or selected parts of the spectrum can be removed, as is done with the gaussian noise filter. The power of Haar wavelet filters is that they can be efficiently calculated and they provide a lot of flexibility. They can potentially leave more detail in the time series, compared to the mean or median filter. To the extent that this detail is useful for an application, the wavelet filter is a better choice.

Limitations of the Haar Wavelet Transform

The Haar wavelet transform has a number of advantages:

The Haar transform also has limitations, which can be a problem for some applications.

In generating each set of averages for the next level and each set of coefficients, the Haar transform performs an average and difference on a pair of values. Then the algorithm shifts over by two values and calculates another average and difference on the next pair.

The high frequency coefficient spectrum should reflect all high frequency changes. The Haar window is only two elements wide. If a big change takes place from an even value to an odd value, the change will not be reflected in the high frequency coefficients.

For example, in the 64 element time series graphed below, there is a large drop between elements 16 and 17, and elements 44 and 45.

Since these are high frequency changes, we might expect to see them reflected in the high frequency coefficients. However, in the case of the Haar wavelet transform the high frequency coefficients miss these changes, since they are on even to odd elements.

The surface below shows three coefficient spectrum: 32, 16 and 8 (where the 32 element coefficient spectrum is the highest frequency). The high frequency spectrum is plotted on the leading edge of the surface. the lowest frequency spectrum (8) is the far edge of the surface.

Note that both large magnitude changes are missing from the high frequency spectrum (32). The first change is picked up in the next spectrum (16) and the second change is picked up in the last spectrum in the graph (8).

Many other wavelet algorithms, like the Daubechies wavelet algorithm, use overlapping windows, so the high frequency spectrum reflects all changes in the time series. Like the Haar algorithm, Daubechies shifts by two elements at each step. However, the average and difference are calculated over four elements, so there are no "holes".

The graph below shows the high frequency coefficient spectrum calculated from the same 64 element time series, but with the Daubechies D4 wavelet algorithm. Because of the overlapping averages and differences the change is reflected in this spectrum.

The 32, 16 and 8 coefficient spectrums, calculated with the Daubechies D4 wavelet algorithm, are shown below as a surface. Note that the change in the time series is reflected in all three coefficient spectrum.

Wavelets and Parallelism

Wavelet algorithms are naturally parallel. For example, if enough processing elements exist, the wavelet transform for a particular spectrum can be calculated in one step by assigning a processor for every two points. The parallelism in the wavelet algorithm makes it attractive for hardware implementation.

Java Source Code Download

The Web page for downloading the Haar wavelet source code can be found here. This Java code is extensively documented and this web page includes a link to the Javadoc generated documentation.

A simpler version of the Haar wavelet algorithm can be found via my web page The Wavelet Lifting Scheme.

Resources

References

Books

Web based references

Disclaimer

This web page was written on nights and weekends, using my computer resources. This Web page does not necessarily reflect the views of my employer (at the time this web page was written). Nothing published here should be interpreted as a reflection on any techniques used by my employer (at that time).

Ian Kaplan, July 2001
Revised: February 2004