Application of wavelets to time-series-based anomaly detection algorithms I've been beginning to work my way through Statistical Data Mining Tutorials by Andrew Moore (highly recommended for anyone else first venturing into this field).  I started by reading this extremely interesting PDF entitled "Introductory overview of time-series-based anomaly detection algorithms" in which Moore traces through many of the techniques used in the creation of an algorithm to detect disease outbreaks.  Halfway through the slides, on page 27, he lists a number of other "state of the art methods" used to detect outbreaks.  The first one listed is wavelets.  Wikipeida describes a wavelet as

a wave-like oscillation with an
  amplitude that starts out at zero,
  increases, and then decreases back to
  zero. It can typically be visualized
  as a "brief oscillation"

but does not describe their application to statistics and my Google searches yield highly academic papers that assume a knowledge of how wavelets relate to statistics or full books on the subject.
I would like a basic understanding of how wavelets are applied to time-series anomaly detection, much in the way Moore illustrates the other techniques in his tutorial.  Can someone provide an explanation of how detection methods using wavelets work or a link to an understandable article on the matter?
 A: Most commonly used and implemented discrete wavelet basis functions (as distinct from the CWT described in Robin's answer) have two nice properties that make them useful for anomaly detection:


*

*They're compactly supported.

*They act as band-pass filters with the pass-band determined by their support.


What this means in practical terms is that your discrete wavelet decomposition looks at local changes in the signal across a variety of scales and frequency bands.  If you have (for instance) large-magnitude, high-frequency noise superimposed across a function that displays a low-magnitude shift over a longer period, the wavelet transform will efficiently separate these two scales and let you see the baseline shift that many other techniques will miss; a shift in this baseline can suggest a disease outbreak or some other change of interest.  In a lot of ways, you can treat the decomposition itself as a smoother (and there's been quite a bit of work done on efficient shrinkage for wavelet coefficients in nonparametric estimation, see e.g. pretty much anything on wavelets by Donoho).  Unlike pure frequency-based methods, the compact support means that they're capable of handling non-stationary data.  Unlike purely time-based methods, they allow for some frequency-based filtering.
In practical terms, to detect anomalies or change points, you would apply a discrete wavelet transform (probably the variant known either as the "Maximum Overlap DWT" or "shift invariant DWT", depending on who you read) to the data, and look at the lower-frequency sets of coefficients to see if you have significant shifts in the baseline.  This will show you when a long-term change is occurring underneath any day-to-day noise.  Percival and Walden (see references below) derive a few tests for statistically significant coefficients that you could use to see if a shift like this is significant or not.
An excellent reference work for discrete wavelets is Percival and Walden, "Wavelet Methods for Time Series Analysis".  A good introductory work is "Introduction to wavelets and wavelet transforms, a primer" by Burrus, Gopinath, and Guo.  If you're coming from an engineering background, then "Elements of wavelets for engineers and scientists" is a good introduction from a signal-processing point of view.
(Edited to include Robin's comments)
A: Wavelets are useful to detect singularities in a signal (see for example the paper here (see figure 3 for an illustration) and the references mentioned in this paper.  I guess singularities can sometimes be an anomaly? 
The idea here is that the Continuous wavelet transform (CWT) has maxima lines that propagates along frequencies, i.e. the longer the line is, the higher is the singularity. See Figure 3 in the paper to see what I mean! note that there is free Matlab code related to that paper, it should be here.

Additionally, I can give you some heuristics detailing why the DISCRETE (preceding example is about the continuous one) wavelet transform (DWT) is interesting for a statistician (excuse non-exhaustivity) :   


*

*There is a wide class of (realistic (Besov space)) signals that are transformed into a sparse sequence by the wavelet transform. (compression property)

*A wide class of (quasi-stationary) processes that are transformed into a sequence with almost uncorrelated features (decorrelation property)

*Wavelet coefficients contain information that is localized in time and in frequency (at different scales). (multi-scale property)

*Wavelet coefficients of a signal concentrate on its singularities. 

A: The list in the presentation that you reference seems fairly arbitrary to me, and the technique that would be used will really depend on the specific problem.  You will note however that it also includes Kalman filters, so I suspect that the intended usage is as a filtering technique.  Wavelet transforms generally fall under the subject of signal processing, and will often be used as a pre-processing step with very noisy data.  An example is the "Multi-scale anomaly detection" paper by Chen and Zhan (see below).  The approach would be to run an analysis on the different spectrum rather than on the original noisy series.
Wavelets are often compared to a continuous-time fourier transform, although they have the benefit of being localized in both time and frequency.  Wavelets can be used both for signal compression and also for smoothing (wavelet shrinkage).  Ultimately, it could make sense to apply a further statistical after the wavelet transform has been applied (by looking in at the auto-correlation function for instance).  One further aspect of wavelets that could be useful for anomaly detection is the effect of localization: namely, a discontinuity will only influence the wavelet that is near it (unlike a fourier transform).  One application of this is to finding locally stationary time series (using an LSW).  
Guy Nason has a nice book that I would recommend if you want to delve further into the practical statistical application: "Wavelet Methods in Statistics with R".  This is specifically targeting the application of wavelets to statistical analysis, and he provides many real world examples along with all the code (using the wavethresh package).  Nason's book does not address "anomaly detection" specifically, although it does do an admiral job of providing a general overview.
Lastly, the wikipedia article does provide many good introductory references, so it is worth going through it in detail.


*

*Xiao-yun Chen, Yan-yan Zhan "Multi-scale anomaly detection algorithm based on infrequent pattern of time series" Journal of Computational and Applied Mathematics Volume 214 ,  Issue 1  (April 2008) 

*G.P. Nason "Wavelet Methods in Statistics with R" Springer, 2008


[As a side note: if you are looking for a good modern technique for change point detection, I would suggest trying a HMM before spending too much time with wavelet methods, unless you have good reason to be using wavelets in your particular field.  This is based on my personal experience.  There are of course many other nonlinear models that could be considered, so it really depends on your specific problem.]
A: Really nice answers so far!
For the mathematical proof regarding robin's first sentence, (i.e. Wavelets are useful to detect singularities in a signal), originally by Yves Meyer, see Singularity Detection and Processing with Wavelets (Mallat and Hwang, 1992). Not only they are useful, they are guaranteed to concentrate around singularities and make them quantifiable via their Lipschitz measure, kind of an "if and only if" condition.
This said, I'd like to reflect on robin's hypothesis that singularities can be an anomaly, and possibly broaden it by rather saying that, since wavelet representations concentrate more on singularities, the result is generally sparser, and a sparser representation can allow to identify anomalies more reliably (even if just as a consequence of having less parameters).
Of course, not everything can be solved with wavelets, this is not the 90s anymore. Now we throw neural networks at everything!
