13.10 Wavelet Transforms
591
Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)
Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.
Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-
readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs
visit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).
The splitting point b must be chosen large enough that the remaining integral over (b, ∞) is
small. Successive terms in its asymptotic expansion are found by integrating by parts. The
integral over (a, b) can be done using dftint. You keep as many terms in the asymptotic
expansion as you can easily compute. See
[6]
for some examples of this idea. More
powerful methods, which work well for long-tailed functions but which do not use the FFT,
are described in
[7-9]
.
CITED REFERENCES AND FURTHER READING:
Stoer, J., and Bulirsch, R. 1980,
Introduction to Numerical Analysis
(New York: Springer-Verlag),
p. 88. [1]
Narasimhan, M.S. and Karthikeyan, M. 1984,
IEEE Transactions on Antennas & Propagation
,
vol. 32, pp. 404–408. [2]
Filon, L.N.G. 1928,
Proceedings of the Royal Society of Edinburgh
, vol. 49, pp. 38–47. [3]
Giunta, G. and Murli, A. 1987,
ACM Transactions on Mathematical Software
, vol. 13, pp. 97–
107. [4]
Lyness, J.N. 1987, in
Numerical Integration
, P. Keast and G. Fairweather, eds. (Dordrecht:
Reidel). [5]
Pantis, G. 1975,
Journal of Computational Physics
, vol. 17, pp. 229–233. [6]
Blakemore, M., Evans, G.A., and Hyslop, J. 1976,
Journal of Computational Physics
, vol. 22,
pp. 352–376. [7]
Lyness, J.N., and Kaper, T.J. 1987,
SIAM Journal on Scientific and Statistical Computing
,vol.8,
pp. 1005–1011. [8]
Thakkar, A.J., and Smith, V.H. 1975,
Computer Physics Communications
, vol. 10, pp. 73–79. [9]
13.10 Wavelet Transforms
Like the fast Fourier transform (FFT), the discrete wavelet transform (DWT) is
a fast, linear operationthat operates on a data vector whose lengthis an integer power
of two, transforming it into a numerically different vector of the same length. Also
like the FFT, the wavelet transform is invertibleand in fact orthogonal— the inverse
transform, when viewed as a big matrix, is simply the transpose of the transform.
Both FFT and DWT, therefore, can be viewed as a rotation in function space, from
the input space (or time) domain, where the basis functions are the unit vectors e
i
,
or Dirac delta functions in the continuum limit, to a different domain. For the FFT,
this new domain has basis functions that are the familiar sines and cosines. In the
wavelet domain, the basis functions are somewhat more complicated and have the
fanciful names “mother functions” and “wavelets.”
Of course there are an infinity of possible bases for function space, almost all of
them uninteresting! What makes the wavelet basis interesting is that,unlike sines and
cosines, individual wavelet functions are quite localized in space; simultaneously,
like sines and cosines, individual wavelet functions are quite localized in frequency
or (more precisely) characteristic scale. As we will see below, the particular kind
of dual localization achieved by wavelets renders large classes of functions and
operators sparse, or sparse to some high accuracy, when transformed into the wavelet
domain. Analogously with the Fourier domain, where a class of computations, like
convolutions, become computationally fast, there is a large class of computations
