Fast wavelet transform

The fast wavelet transform provides an efficient algorithm for computing the discrete wavelet transform. We will show that provided we know some function fy, then the scaling and wavelet coefficients can be calculated in the absence of the scaling and wavelet functions, avoiding the integral expression in Eqs. (5) and (6). An expression for the scaling coefficients will be derived first, an expression for the wavelet coefficients then follows. 

Let us assume that we know fy, which is expressed as follows 

Since the scaling basis functions in Vj are orthonormal to their translates, 

(7) requires some formulation of ( )j and hence ( )(t) which may be difficult to obtain. It is desirable that an expression for the scaling cj k and wavelet coefficients dj k be attainable without the need to construct (f)(t) or vj/(t). We now set about doing this. First, write 

This is an expression for fy which has projections in Vj and W, ). Now an expression for the scaling coefficients can be written as 

---

Like the FFT, the fast wavelet transform (FWT) is a fast, linear operation that operates on a data vector in which the length is an integer power of two (i.e., a dyadic vector), transforming it into a numerically different vector of the same length. Like the FFT, the FWT is invertible and in fact orthogonal that is, the inverse transform, when viewed as a matrix, is simply the transpose of the transform. Both the FFT and the discrete wavelet transform (DWT) can be regarded as a rotation in function... 

Fast Wavelet Transform (FWT) is a fast algorithm for wavelet transforms that requires only n operations for an -dimensional vector. 

Depezynski, U., Jetter, K., Molt, K and Niemoller, A. (1997) The fast wavelet transform on compact intervals as a tool in chemometrics. I. Mathematical background. Chemom. Intell. Lab. Syst., 39, 19-27. 

Multiresolution analysis (MRA) [7,8,9] provides a concise framework for explaining many aspects of wavelet theory such as how wavelets can be constructed [1,10]. MRA provides greater insight into the representation of functions using wavelets and helps establish a link between the discrete wavelet transform of continuous functions and discrete signals. MRA also allows for an efficient algorithm for implementing the discrete wavelet transform. This is called the fast wavelet transform and follows a pyramidal... 

As for orthogonal wavelets, a fast wavelet transform exists for computing the scaling and wavelet coefficients. Provided the scaling and wavelet coefficients are known for some scale, the scaling and wavelet coefficients at the next lower scale j - 1, are computed as follows ... 

A. Cohen, I. Daubechies and V. Pierre, Wavelets on the Interval and Fast Wavelet Transforms, Appl Comput. Harmonic Analysis, 1 (1993), 54-81. 

We first consider redefining a multiresolution to cater for situations when functions are rescaled by a general factor m > 2 and then show how the fast wavelet transform (or pyramidal algorithm) is performed for higher multiplicity wavelets. 

Up to December 1998, more than 30 publications have reported spectroscopic studies with the use of a WT algorithm [9,10], Within this work, WT has been utilized in three major areas that include data denoising, data compression, and pattern recognition. Two classes of wavelet algorithm namely discrete wavelet transform (DWT) and wavelet packet transform (WPT), have been commonly adopted in the computation. The former one is also known as the fast wavelet transform (FWT). The general theory on both FWT and WPT can be found in other Chapters of this book and some chemical journals [16-18], and is not repeated here. In the following sections, selected applications of WT in different spectral techniques will be described. 

F.T. Chau, T.M. Shih, J.B. Gao and C.K. Chan. Application of the Fast Wavelet Transform Method to Compress Ultraviolet-Visible Spectra. Applied Spectroscopy. 50(1996), 339-349. 

F-T. Chau, J.B. Gao, T.M. Shih and J. Wang, Compression of Infrared Spectral Data Using the Fast Wavelet Transform Method, Applied Spectro.scopy, 51 (1997), 649-659. 

U. Depczynski, K. Jetter, K. Molt and A. Niemoller, The Fast Wavelet Transform on Compact Intervals as a Tool in Chemometrics. 1. Mathematical Background, Chemometrics and Intelligent Laboratory Systems, 39 (1997), 19-27. 

In this chapter, compression is achieved by assuming that the data profiles can be approximated by a linear combination of smooth basis functions. The bases used originate from the fast wavelet transform. The idea that data sets are really functions rather than discrete vectors is the main focus of functional data analysis [12-15] which forms the foundation for the generation of parsimonious models. 

There is a whole family of different wavelet methods available depending on the signal properties and the type of information that is to be extracted. However, this chapter will only focus on the fast wavelet transform (FWT) which is based on Mallat s algorithm [39.40]. It should be mentioned that the described methods to achieve parsimonious models are not dependent on one particular type of wavelet transform. Other types of wavelet transforms can be used. FWT is not always optimal for all types of problems and other techniques such as wavelet packets [41], continuous transforms [42,43] and biorthogonal transforms [37] should be considered. Some of the properties of the FWT that makes it an attractive transform are ... 

Let us now consider regression in general in terms of a matrix formulation of the fast wavelet transform. 

The FWT basis malri.x. The fast wavelet transform (FWT) can be formulated in terms of matrix algebra by storing each of the wavelet functions in the time/wavelength domain in a matrix B. This matrix contains all the translations and dilations of the wavelet necessary to perform a full transform. One common way to organise this matrix is to sort the sets of shifted basis... 

G. Beylkin, R. Coifman, V. Rokhlin, Fast Wavelet Transforms and Numerical Algorithms I, Communications of the Pure Applied Mathematics, XLIV (1991), 141. 

Because of the recursive quadrisection process by which these sampling patterns are built, we can build fast hierarchical transforms. These generalize the fast wavelet transform to the surface setting. While it is much harder to prove smoothness and approximation properties in this more general setting, first re-... 

This construction ensures the wavelets and their associated scaling functions to be orthogonal. The scaling and wavelet equation provide a simple tool to derive the fast wavelet transform. If / Z f )) and if we denote scaling coefficients of function/ by yjji, and... 

These equations form the decomposition algorithm. The decomposition algorithm is the first half of the fast wavelet transform. If we go also in the opposite direction we can reconstruct coefficients yj+ 2k+i from coefficients andy, t at the previous scale as follows ... 

Now we have complete fast wavelet transform. It can be performed in 0(n) operations, and it captures not... 

If Wj is the orthogonal complement we obtain orthogonal wavelets [9]. In this case the transformation T , which relates the single and the multiscale coefficients is the Fast Wavelet Transform [5]. If V is a multiresolution analysis, then a refinement equation is valid for < ... 

To avoid the evaluation of these quantities, the continuous phase equilibrium function is expressed in terms of the single-space basis e.g. K T,p, F ) G Vn- Using the fast Wavelet transform T the single-scale representation of the trial solution is obtained and the residuum of (1.3) can be formulated in terms of the single-scale basis The residuum is thus expressed by means of scaling functions of common level n. A subsequent fast wavelet transform provides the residuum of (1.3) in the multiscale representation, whose inner products with the weight functions can easily be evaluated due to orthogonality. This approach exactly recovers the discrete model without any deviations due to the continuous model formulation if the Haar basis is used. 

The Fast Wavelet Transform on Compact Intervals as a Tool in Chemometrics. I. Mathematical Bacl ound. 

Compression of Infrared Spectral Data Using the Fast Wavelet Transform Method. 

F. T. Chau, T. M. Shih, J. B. Gao, C. K. Chan. Application of the fast wavelet transform method to compress ultraviolet-visible spectra. Appl Spectrosc 50 339, 1996. 

---