Wavelet transforms versus Fourier transforms
HTML articles powered by AMS MathViewer
- by Gilbert Strang PDF
- Bull. Amer. Math. Soc. 28 (1993), 288-305 Request permission
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.References
- Alfred Haar, Zur Theorie der orthogonalen Funktionensysteme, Math. Ann. 69 (1910), no. 3, 331–371 (German). MR 1511592, DOI 10.1007/BF01456326
- J. L. Walsh, A Closed Set of Normal Orthogonal Functions, Amer. J. Math. 45 (1923), no. 1, 5–24. MR 1506485, DOI 10.2307/2387224
- Richard E. Blahut, Fast algorithms for digital signal processing, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1985. MR 777867
- Charles Van Loan, Computational frameworks for the fast Fourier transform, Frontiers in Applied Mathematics, vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1153025, DOI 10.1137/1.9781611970999
- Gilbert Strang, Introduction to applied mathematics, Wellesley-Cambridge Press, Wellesley, MA, 1986. MR 870634
- William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling, Numerical recipes, Cambridge University Press, Cambridge, 1986. The art of scientific computing. MR 833288
- P. Duhamel and M. Vetterli, Fast Fourier transforms: a tutorial review and a state of the art, Signal Process. 19 (1990), no. 4, 259–299 (English, with French and German summaries). MR 1048328, DOI 10.1016/0165-1684(90)90158-U G. Strang, Introduction to linear algebra, Wellesley-Cambridge Press, Wellesley, MA, 1993.
- Ingrid Daubechies, Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math. 41 (1988), no. 7, 909–996. MR 951745, DOI 10.1002/cpa.3160410705
- P. G. Lemarié (ed.), Les ondelettes en 1989, Lecture Notes in Mathematics, vol. 1438, Springer-Verlag, Berlin, 1990 (French). Abstracts from the Seminar on Harmonic Analysis held at the Université de Paris-Sud, Orsay, January–March 1989. MR 1083578, DOI 10.1007/BFb0083510
- Stephane G. Mallat, Multiresolution approximations and wavelet orthonormal bases of $L^2(\textbf {R})$, Trans. Amer. Math. Soc. 315 (1989), no. 1, 69–87. MR 1008470, DOI 10.1090/S0002-9947-1989-1008470-5
- Ingrid Daubechies and Jeffrey C. Lagarias, Two-scale difference equations. I. Existence and global regularity of solutions, SIAM J. Math. Anal. 22 (1991), no. 5, 1388–1410. MR 1112515, DOI 10.1137/0522089
- Ingrid Daubechies and Jeffrey C. Lagarias, Sets of matrices all infinite products of which converge, Linear Algebra Appl. 161 (1992), 227–263. MR 1142737, DOI 10.1016/0024-3795(92)90012-Y
- Gian-Carlo Rota and Gilbert Strang, A note on the joint spectral radius, Nederl. Akad. Wetensch. Proc. Ser. A 63 = Indag. Math. 22 (1960), 379–381. MR 0147922, DOI 10.1016/S1385-7258(60)50046-1
- Marc A. Berger and Yang Wang, Bounded semigroups of matrices, Linear Algebra Appl. 166 (1992), 21–27. MR 1152485, DOI 10.1016/0024-3795(92)90267-E
- David Colella and Christopher Heil, Characterizations of scaling functions: continuous solutions, SIAM J. Matrix Anal. Appl. 15 (1994), no. 2, 496–518. MR 1266600, DOI 10.1137/S0895479892225336
- Timo Eirola, Sobolev characterization of solutions of dilation equations, SIAM J. Math. Anal. 23 (1992), no. 4, 1015–1030. MR 1166573, DOI 10.1137/0523058
- Lars F. Villemoes, Energy moments in time and frequency for two-scale difference equation solutions and wavelets, SIAM J. Math. Anal. 23 (1992), no. 6, 1519–1543. MR 1185640, DOI 10.1137/0523085
- Gilbert Strang, Wavelets and dilation equations: a brief introduction, SIAM Rev. 31 (1989), no. 4, 614–627. MR 1025484, DOI 10.1137/1031128 O. Rioul and M. Vetterli, Wavelets and signal processing, IEEE Signal Processing Mag. 8 (1991), 14-38. M. Vetterli and C. Herley, Wavelets and filter banks: theory and design, IEEE Trans. Acoust. Speech Signal Process. 40 (1992), 2207-2232. 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. P. Heller, Regular M-band wavelets, SIAM J. Matrix Anal. Appl. (to appear).
- Ingrid Daubechies, Ten lectures on wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1162107, DOI 10.1137/1.9781611970104
- F. Schipp, W. R. Wade, and P. Simon, Walsh series, Adam Hilger, Ltd., Bristol, 1990. An introduction to dyadic harmonic analysis; With the collaboration of J. Pál. MR 1117682
- Yves Meyer, Ondelettes et opérateurs. I, Actualités Mathématiques. [Current Mathematical Topics], Hermann, Paris, 1990 (French). Ondelettes. [Wavelets]. MR 1085487
- Ronald A. DeVore and Bradley J. Lucier, Wavelets, Acta numerica, 1992, Acta Numer., Cambridge Univ. Press, Cambridge, 1992, pp. 1–56. MR 1165722, DOI 10.1017/s0962492900002233 N. S. Jayant and P. Noll, Digital coding of waveforms, Prentice-Hall, Englewood Cliffs, NJ, 1984. T. Hopper and F. Preston, Compression of grey-scale fingerprint images, Data Compression Conference, IEEE Computer Society Press, New York, 1992. M. V. Wickerhauser, High-resolution still picture compression, preprint. M. V. Wickerhauser and R. R. Coifman, Entropy based methods for best basis selection, IEEE Trans. Inform. Theory 38 (1992), 713-718.
- Ronald A. DeVore, Björn Jawerth, and Bradley J. Lucier, Image compression through wavelet transform coding, IEEE Trans. Inform. Theory 38 (1992), no. 2, 719–746. MR 1162221, DOI 10.1109/18.119733 J. N. Bradley and C. Brislawn, Compression of fingerprint data using the wavelet vector quantization image compression algorithm, Los Alamos Report 92-1507, 1992. J. Lim, Two-dimensional signal and image processing, Prentice-Hall, Englewood Cliffs, NJ, 1990.
- G. Beylkin, R. Coifman, and V. Rokhlin, Fast wavelet transforms and numerical algorithms. I, Comm. Pure Appl. Math. 44 (1991), no. 2, 141–183. MR 1085827, DOI 10.1002/cpa.3160440202
- Charles K. Chui, An introduction to wavelets, Wavelet Analysis and its Applications, vol. 1, Academic Press, Inc., Boston, MA, 1992. MR 1150048
- Mary Beth Ruskai and Gregory Beylkin (eds.), Wavelets and their applications, Jones and Bartlett Publishers, Boston, MA, 1992. MR 1187335
- Jeffrey S. Geronimo, Douglas P. Hardin, and Peter R. Massopust, Fractal functions and wavelet expansions based on several scaling functions, J. Approx. Theory 78 (1994), no. 3, 373–401. MR 1292968, DOI 10.1006/jath.1994.1085
Additional Information
- © Copyright 1993 American Mathematical Society
- 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