Wavelet transforms versus Fourier transforms

Author:
Gilbert Strang

Journal:
Bull. Amer. Math. Soc. **28** (1993), 288-305

MSC:
Primary 42C15; Secondary 65T20, 94A11

DOI:
https://doi.org/10.1090/S0273-0979-1993-00390-2

MathSciNet review:
1191480

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This note is a very basic introduction to wavelets. It starts with an orthogonal basis of piecewise constant functions, constructed by dilation and translation. The "wavelet transform" maps each *f(x)* to its coefficients with respect to this basis. The mathematics is simple and the transform is fast (faster than the Fast Fourier Transform, which we briefly explain), but approximation by piecewise constants is poor. To improve this first wavelet, we are led to dilation equations and their unusual solutions. Higher-order wavelets are constructed, and it is surprisingly quick to compute with them -- always indirectly and recursively.

We comment informally on the contest between these transforms in signal processing, especially for video and image compression (including high-definition television). So far the Fourier Transform -- or its 8 by 8 windowed version, the Discrete Cosine Transform -- is often chosen. But wavelets are already competitive, and they are ahead for fingerprints. We present a sample of this developing theory.

**[1]**A. Haar,*Zur Theorie der orthogonalen Funktionensysteme*, Math. Ann.**69**(1910), 331-371. MR**1511592****[2]**J. L. Walsh,*A closed set of normal orthogonal functions*, Amer. J. Math.**45**(1923), 5-24. MR**1506485****[3]**R. E. Blahut,*Fast algorithms for digital signal processing*, Addison-Wesley, New York, 1984. MR**777867 (86h:94005)****[4]**C. Van Loan,*Computational frameworks for the fast Fourier transform*, SIAM, Philadelphia, PA, 1992. MR**1153025 (93a:65186)****[5]**G. Strang,*Introduction to applied mathematics*, Wellesley-Cambridge Press, Wellesley, MA, 1986. MR**870634 (88a:00006)****[6]**W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling,*Numerical recipes*, Cambridge Univ. Press, Cambridge, 2nd ed., 1993. MR**833288 (87m:65001a)****[7]**P. Duhamel and M. Vetterli,*Fast Fourier transforms: a tutorial review*, Signal Processing**19**(1990), 259-299. MR**1048328 (91a:94004)****[8]**G. Strang,*Introduction to linear algebra*, Wellesley-Cambridge Press, Wellesley, MA, 1993.**[9]**I. Daubechies,*Orthogonal bases of compactly supported wavelets*, Comm. Pure Appl. Math.**41**(1988), 909-996. MR**951745 (90m:42039)****[10]**P. G. Lemarié (ed.),*Les ondelettes en 1989*, Lecture Notes in Math., vol. 1438, Springer-Verlag, New York, 1990. MR**1083578 (92g:42018)****[11]**S. Mallat,*Multiresolution approximations and wavelet orthogonal bases of*, Trans. Amer. Math. Soc.**315**(1989), 69-88;*A theory for multiresolution approximation: the wavelet representation*, IEEE Trans. PAMI**11**(1989), 674-693. MR**1008470 (90e:42046)****[12]**I. Daubechies and J. Lagarias,*Two-scale difference equations*: I.*Existence and global regularity of solutions*, SIAM J. Math. Anal.**22**(1991), 1388-1410; II.*Local regularity, infinite products of matrices and fractals*, SIAM J. Math. Anal.**23**(1992), 1031-1079. MR**1112515 (92d:39001)****[13]**-,*Sets of matrices all infinite products of which converge*, Linear Algebra Appl.**161**(1992), 227-263. MR**1142737 (93f:15006)****[14]**G.-C. Rota and G. Strang,*A note on the joint spectral radius*, Kon. Nederl. Akad. Wet. Proc. A**63**(1960), 379-381. MR**0147922 (26:5434)****[15]**M. Berger and Y. Wang,*Bounded semigroups of matrices*, Linear Algebra Appl.**166**(1992), 21-28. MR**1152485 (92m:15012)****[16]**D. Colella and C. Heil,*Characterizations of scaling functions*, I.*Continuous solutions*, SIAM J. Matrix Anal. Appl.**15**(1994) (to appear). MR**1266600 (95f:26004)****[17]**T. Eirola,*Sobolev characterization of solutions of dilation equations*, SIAM J. Math. Anal.**23**(1992), 1015-1030. MR**1166573 (93f:42056)****[18]**L. F. Villemoes,*Energy moments in time and frequency for two-scale difference equation solutions and wavelets*, SIAM J. Math. Anal.**23**(1992), 1519-1543. MR**1185640 (94c:39002)****[19]**G. Strang,*Wavelets and dilation equations: a brief introduction*, SIAM Review**31**(1989), 614-627. MR**1025484 (91m:42028)****[20]**O. Rioul and M. Vetterli,*Wavelets and signal processing*, IEEE Signal Processing Mag.**8**(1991), 14-38.**[21]**M. Vetterli and C. Herley,*Wavelets and filter banks: theory and design*, IEEE Trans. Acoust. Speech Signal Process.**40**(1992), 2207-2232.**[22]**P. P. Vaidyanathan,*Multirate digital filters, filterbanks, polyphase networks, and applications: a tutorial*, Proc. IEEE**78**(1990), 56-93;*Multirate systems and filter banks*, Prentice-Hall, Englewood Cliffs, NJ, 1993.**[23]**P. Heller,*Regular M-band wavelets*, SIAM J. Matrix Anal. Appl. (to appear).**[24]**I. Daubechies,*Ten lectures on wavelets*, SIAM, Philadelphia, PA, 1992. MR**1162107 (93e:42045)****[25]**F. Schipp, W. R. Wade, and P. Simon,*Walsh series*, Akad. Kaidó and Adam Hilger, Budapest and Bristol, 1990. MR**1117682 (92g:42001)****[26]**Y. Meyer,*Ondelettes et opérateurs*, Hermann, Paris, 1990;*Wavelets*, translation to be published by Cambridge Univ. Press. MR**1085487 (93i:42002)****[27]**R. DeVore and B. J. Lucier,*Wavelets*, Acta Numerica**1**(1991), 1-56. MR**1165722 (93g:42022)****[28]**N. S. Jayant and P. Noll,*Digital coding of waveforms*, Prentice-Hall, Englewood Cliffs, NJ, 1984.**[29]**T. Hopper and F. Preston,*Compression of grey-scale fingerprint images*, Data Compression Conference, IEEE Computer Society Press, New York, 1992.**[30]**M. V. Wickerhauser,*High-resolution still picture compression*, preprint.**[31]**M. V. Wickerhauser and R. R. Coifman,*Entropy based methods for best basis selection*, IEEE Trans. Inform. Theory**38**(1992), 713-718.**[32]**R. DeVore, B. Jawerth, and B. J. Lucier,*Image compression through wavelet transform coding*, IEEE Trans. Inform. Theory**38**(1992), 719-746. MR**1162221 (97h:68139)****[33]**J. N. Bradley and C. Brislawn,*Compression of fingerprint data using the wavelet vector quantization image compression algorithm*, Los Alamos Report 92-1507, 1992.**[34]**J. Lim,*Two-dimensional signal and image processing*, Prentice-Hall, Englewood Cliffs, NJ, 1990.**[35]**G. Beylkin, R. R. Coifman, and V. Rokhlin,*Fast wavelet transforms and numerical algorithms*, Comm. Pure Appl. Math.**44**(1991), 141-183. MR**1085827 (92c:65061)****[36]**C. K. Chui,*An introduction to wavelets*, Academic Press, New York, 1992. MR**1150048 (93f:42055)****[37]**M. B. Ruskai et al.,*Wavelets and their applications*, Jones and Bartlett, Boston, 1992. MR**1187335 (93e:00031)****[38]**J. S. Geronimo, D. P. Hardin, and P. R. Massopust,*Fractal functions and wavelet expansions based on several scaling functions*(to appear). MR**1292968 (95h:42033)**

Retrieve articles in *Bulletin of the American Mathematical Society*
with MSC:
42C15,
65T20,
94A11

Retrieve articles in all journals with MSC: 42C15, 65T20, 94A11

Additional Information

DOI:
https://doi.org/10.1090/S0273-0979-1993-00390-2

Keywords:
Wavelets,
Fourier transform,
dilation,
orthogonal basis

Article copyright:
© Copyright 1993
American Mathematical Society