Applied & Computational Harmonic Analysis:
Comments, Handouts, and References Page (Winter 2010)
Course: MAT 271
CRN: 63579
Title: Applied & Computational Harmonic Analysis
Class: MW 5:10pm-6:30pm, 2112 Math. Sci. Bldg.
Instructor: Naoki Saito
Office: 2142 MSB
Phone: 754-2121
Email:saito@math.ucdavis.edu
Office Hours: MW 3:10pm-4:00pm, or by appointment
The following references are useful and contains much more
details of the topics covered or referred to in my lectures.
I strongly encourage you to take a look at some of them.
Lecture 1: Overture and Motivation;
What is a Signal?
Good references on basic Fourier analysis, in particular, the Fourier transforms:
- H. Dym & H. McKean: Fourier Series and Integrals, Academic Press, 1972. Chap. 2.
- G. B. Folland: Fourier Analysis and Its Applications,
AMS, 1992. Chap. 7.
- M. A. Pinsky: Introduction to Fourier Analysis and Wavelets,
AMS, 2002. Chap. 2.
For quantization, which will not be discussed in this course due to the
time constraint, see: - R. M. Gray and D. L. Neuhoff: "Quantization," IEEE Trans. Inform.
Theory, vol. 44, no.6, pp.2325-2383, 1998.
- K. Sayood: Introduction to Data Compression, 3rd Ed., Morgan
Kaufmann Publ., 2006. In particular, Chapters 8 & 9.
If you are interested in vision science, I would strongly recommend the following books:
-
D. H. Hubel: Eye, Brain, and Vision, Scientific American Library, 1995.
-
B. A. Wandell: Foundation of Vision, Sinauer Associates, Inc., 1995.
Lecture 2: Basics of the Fourier Transforms
Denoising Enrico Caruso's recording (through the courtesy of Maxim Goldberg) we listened in the class was due to the following paper:
-
J. Berger, M. Goldberg, & R. Coifman:
"Removing Noise from Music Using Local Trigonometric Bases and Wavelet Packets,"
Journal of the Audio Engineering Society, vol.42, no.10, pp.808-818, 1994.
Lecture 3: Fourier Transforms in L2; The Heisenberg Uncertainty Principle
Details of the L2 theory:
- Dym & McKean: Sec. 2.3-2.5.
- Pinsky: Sec. 2.4.
- G. B. Folland: Real Analysis, 2nd Ed., Wiley
Interscience, 1999. Sec. 8.3.
- E. M. Stein & G. L. Weiss: Introduction to Fourier
Analysis on Euclidean Spaces, Princeton Univ. Press, 1970. Sec. 1.2.
Basic references on the Heisenberg inequality/uncertainty principle:
- Dym & McKean: Sec. 2.8.
- Folland: Fourier Analysis, Sec. 7.3.
- Pinsky: Sec. 2.4.3.
Lecture 4: Bandlimited Functions and Sampling Theorems; Periodization vs Sampling; Fourier Series
Sampling Theorems: - R. N. Bracewell: The Fourier
Transform and Its Applications, 2nd Ed., Revised, McGraw-Hill,
1987. Chap. 10.
- W. L. Briggs & V. E. Henson: The DFT: An Owner's Manual
for the Discrete Fourier Transform, SIAM, 1995. Sec. 3.4, Chap. 6.
- Pinsky: Chap.4.
- See also a nice interactive java demonstration by Matt Herman on sampling and aliasing.
For more details on Sampling Theorems and Non-Uniform Sampling Schemes,
see: - H. J. Landau: "Sampling, data transmission, and the Nyquist rate," Proc. IEEE, vol.55, no.10, pp.1701-1706, 1967.
- A. Aldroubi and K. Gröchenig, "Nonuniform sampling and reconstruction in shift-invariant spaces," SIAM Review, vol.43, no.4, pp.585-620, 2001.
For the historical articles on the sampling theorems, see: - E. T.
Whittaker: "On the functions which are represented by the expansions of
the interpolation-theory," Proc. Royal Soc. Edinburgh, Sec. A,
vol.35, pp.181-194, 1915.
- C. E. Shannon: "Communication in the presence of noise," Proc.
IRE, vol.37, pp.10-21, 1949.
- E.Meijering: "A chronology of interpolation: From ancient astronomy to modern signal and image processing," Proc. IEEE, vol.90, no.3, pp.319-342, 2002.
For the other stuff I menioned in the class, the details
can be found as follows:
Orthogonal Polynomials:
- G. Szegö: Orthogonal Polynomials, 4th
Ed., AMS, 1975.
- Folland: Fourier Analysis, Chap. 6.
Lecture 5: Smoothness of Functions and Decay Rate of the
Fourier Coefficients; Functions of Bounded Variation
On the Basel Problem ∑ k-2 =
π2/6, Euler, different proofs, etc.
- W. Dunham: Euler: The Master of Us All, Math. Assoc. Amer., 1999.
Chap.3.
- R. Ayoub: "Euler and the zeta function," Amer. Math. Monthly, vol.81, no.10, pp.1067-1086, 1974.
- Dan Kalman: "Six ways to sum a series," College Math. Jour., vol.24, no.5, pp.402-421, 1993.
Smoothness Class Hierarchy: - P. J. Davis and P.
Rabinowitz: Methods of Numerical
Integration, Academic Press, 1984 (Reprinted by Dover Pub. Inc., 2007)
Sec. 1.9.
The definition of BV in higher dimensions can be found in: - L. C.
Evans and R. F. Gariepy: Measure Theory and Fine
Properties of
Functions, CRC Press, 1992, Chap.5.
Lecture 6: Functions of Bounded Variations and the Decay Rate of the
Fourier Coefficients II; Fourier Series on Intervals; Discrete Fourier Transform I
Functions of Bounded Variation, the Fourier Coefficients:
- C. Lanczos: Discourse on Fourier Series, Hafner
Publishing Co., New York, 1966. Sec 2. This is the best book on 1D
Fourier series from the applied perspective. Unfortunately, this book
is out of print.
- V. I. Smirnov: A Course of Higher Mathematics, Vol. V,
Pergamon Press, 1964, Chap. 1. This is out of print too.
- M.Taibleson: "Fourier coefficients of functions of bounded variation," Proc. Amer. Math. Soc., vol.18, pp.766, 1967.
Fourier Series on Intervals, Fourier Cosine and Sine Series: -
Folland: Fourier Analysis, Sec. 2.4.
- C. Lanczos: Applied Analysis, Prentice-Hall, Inc., 1956,
Reprinted by Dover, 1988, Sec. 4.5. This book is still in print. I
strongly urge you to buy this book and read it from cover to cover!
Lecture 7: Discrete Fourier Transform II
For advanced topics on DFT, check out the following articles and book:
- J. H. McClellan ad T. W. Parks: "Eigenvalue and eigenvector decomposition of the discrete Fourier transform," IEEE Trans. Audio and
Electroacoustics, vol.AU-20, no.1, pp.66-74, 1972 (with comments, vol.AU-21, no.1, pp.65, 1973).
-
L. Auslander and R. Tolimieri: "Is computing with the finite Fourier transform pure or applied mathematics?" Bull. AMS, vol.1, no.6, pp.847-897, 1979.
- A. Terras: Fourier Analysis on Finite Groups and Applications,
London Mathematical Society Student Texts vol.43, Cambridge Univ.Press,
1999.
Relationship between Fourier Series, DFT, and Trigonometric
Interpolation: - C. Lanczos: Discourse on Fourier Series,
Hafner Publishing Co., New York, 1966. Sec 17.
- I. P. Natanson: "On the convergence of trigonometrical interpolation at
equi-distant knots," Annals of Math., vol.45, no.3, pp.457-471, 1944.
- J. P. Boyd: Chebyshev and Fourier Spectral Methods, 2nd Ed., Dover, 2001. Chapter 4, in particular, Sec.4.5.
- D. M. Young and R. T. Gregory: A Survey of Numerical
Mathematics, Vol. I, Addison-Wesley, 1972, pp.329-339.
Lecture 8: Fast Fourier Transform (FFT)
There are many references on FFT, but the following are particularly
useful: -
J. W. Cooley and J. W. Tukey: "An algorithm for the machine
calculation of complex Fourier series," Math. Comput., vol.19,
pp.297-301, 1965.
- Briggs & Henson: Chap. 10.
- C. F. Van Loan: Computational Frameworks for the Fast Fourier
Transform, SIAM, 1992.
- W. T. Cochran et al.: "What is the Fast Fourier Transform?", Proc. IEEE, vol.55, no.10, pp.1664-1674, 1967.
Perhaps, the best FFT public software package is: - FFTW, which also includes
higher dimensional FFT as well as DCT/DST.
Lecture 9: Discrete Cosine & Sine Transforms (DCT/DST)
For basic and important references on DCT/DST are:
- N. Ahmed, T. Natarayan, and K. R. Rao: "Discrete cosine transform," IEEE Trans. Comput., vol.COM-23, pp.90-93, 1974.
- K. R. Rao and P. Yip: Discrete Cosine Transform: Algorithms,
Advantages, and Applications, Academic Press, 1990.
- G. Strang: "The discrete cosine transform," SIAM Review, vol.41, no.1, pp.135-147, 1999.
- M. V. Wickerhauser: Adapted Wavelet Analysis from Theory to
Software, A K Peters, Ltd., 1994. Chap. 3.
For the Sturm-Liouville Theory I referred to in today's lecture,
the following are nice references:
- Folland: Fourier Analysis: Sec.3.5, 3.6, 7.4.
- Dym & McKean: Sec. 1.7, 1.9.
- R. Courant & D. Hilbert: Methods of Mathematical Physics,
Vol. I, First English Edition, John Wiley & Sons, 1953.
Republished as Wiley Classics Library in 1989. See Chap. V
in particular.
Lecture 10: Karhunen-Loève Transform (KLT)
Discrete version (aka Principal Component Analysis [PCA]): -
K. Fukunaga: Introduction to Statistical Pattern Recognition,
2nd Edition, Academic Press, 1990. Chap. 9, Appendix A.
- K. V. Madia, J. T. Kent, and J. M. Bibby: Multivariate
Analysis, Academic Press, 1979. Chap. 8.
- S. Watanabe: "Karhunen-Loève expansion and factor
analysis: Theoretical remarks and applications," Trans. 4th Prague
Conf. Inform. Theory, Statist. Decision Functions, Random Processes,
Publishing House of the Czechoslovak Academy of Sciences, Prague,
pp.635-660, 1965.
- R. Kannan and S. Vempala:
"Spectral algorithms," Foudations and Trends in Theoretical Computer Science, vol.4, nos.3-4, pp.157-288, 2008.
We only discussed the discrete version in the class, but KLT has its
continuous version. The following are some references: - U.
Grenander: Stochastic processes and statistical inference,
Arkiv för Matematik, vol.1, pp.195-277, 1950.
- W. B. Davenport and W. L. Root: An Introduction to the Theory of
Random Signals and Noise, McGraw Hill, 1958, republished by IEEE
Press, 1987. Chap. 6.
- W. D. Ray and R. M. Driver: "Further decomposition of
the Karhunen-Loève series representation of a stationary random process," IEEE Trans. Inform. Theory, vol.IT-16, no.6, pp.663-668, 1970.
See also: - F. Riesz and B. Sz.-Nagy: Functional Analysis,
Frederic Ungar, 1950, republished by Dover, 1990. Chap. VI.
- Courant & Hilbert: Vol.I, Chap. III.
Lecture 11: Relationship among KLT/PCA, SVD, and DCT
Relationship between KLT/PCA and DCT:
- N. Ahmed, T. Natarayan, and K. R. Rao: "Discrete cosine transform," IEEE Trans. Comput., vol.COM-23, pp.90-93, 1974.
- R. J. Clarke: "Relation between the Karhunen Loève and cosine transforms," IEE Proc., vol.128, Part F, no.6,pp.359-360, 1981.
Basics of Singular Value Decomposition (SVD):
- L. N. Trefethen and D. Bau, III: Numerical Linear Algebra, SIAM, 1997, Chap.4: The Singular Value Decomposition.
- L. N. Trefethen and D. Bau, III: Numerical Linear Algebra, SIAM, 1997, Chap.5: More about the SVD.
- G. H. Golub and C. F. Van Loan: Matrix Computations, 3rd Ed.,
Johns Hopkins Univ. Press, 1996. Sec. 2.5.
- G. W. Stewart: "On the early history of the singular value decomposition," SIAM Review, vol.35, no.4, pp.551-566, 1993.
On Toeplitz matrices: - U. Grenander and G. Szegő: Toeplitz
Forms and Their Applications, 2nd Ed., AMS-Chelsea, 1984.
- R. M.
Gray: Toeplitz and circulant matrices: A review, Technical Report,
Information Systems Laboratory, Department of Electrical Engineering,
Stanford University, 2009.
- H. Widom: "Toeplitz matrices," in Studies in Real and Complex
Analysis (I. I. Hirschman, Jr. ed.), MAA Studies in Mathematics,
1965.
Applications: Eigenfaces/The Rogues Gallery Problem:
- M. Kirby and L. Sirovich, "Application of Karhunen-Loeve procedure for the characterization of human faces," IEEE Trans. Pattern Anal. Machine Intell., vol.12, no.1, pp.103-108, 1990.
- N. Saito: "Image approximation and modeling via least statistically dependent bases", Pattern Recognition, vol.34, no.9, pp.1765-1784, 2001.
Lecture 12: Time-Frequency Analysis and Synthesis; Windowed
(or Short-Time) Fourier Transform
- S. Mallat: A Wavelet Tour of Signal Processing, 3rd Ed.,
Academic Press, 2009. Chap. 4.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992.
Chap.2.
- I. Daubechies: "The wavelet-transform, time-frequency localization and signal analysis," IEEE Trans. Inform. Theory, vol.36, no.5, pp.961-1005, 1990.
Some historical papers:
- D. Gabor: "Theory of communication: Part I: The analysis of information," J. IEE (London), vol.93, no.26, pp.429-441, 1946.
- D. Gabor: "Theory of communication: Part II: The analysis of hearing," J. IEE (London), vol.93, no.26, pp.442-445, 1946.
- D. Gabor: "Theory of communication: Part III: Frequency compression and expansion," J. IEE (London), vol.93, no.26, pp.445-457, 1946.
- J. Ville: "Théorie et applications de la notion de signal
analytique," Cables et Transmissions, 2ème A, no.1,
pp.61-74, 1948.
Lecture 13: Introductory Frame Theory; The Balian-Low Theorem
Some basic references:
- S. Mallat: A Wavelet Tour of Signal Processing, 3rd Ed., Academic Press, 2009. Chap. 5.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992. Chap. 3, 4.
- K.Gröchenig: Foundations of Time-Frequency Analysis,
Birkhäuser, 2001. Chap. 5-7.
- O. Christensen: Frames and Bases: An Introductory Course, Birkhäuser, 2002.
- J.-P. Kahane and P.-G. Lemarié-Rieusset: Fourier Series
and Wavelets, Studies in the Development of Modern Mathematcis,
Vol.3, Gordon and Breach Publishers, 1995. Chap. 1 of the Wavelet portion.
- Course handout on the Balian-Low theorem.
See also the following original papers:
- R. Balian: "Un principe d'incertitude fort en théorie du signal ou en mécanique quantique," C. R. Acad. Sci. Paris, vol.292, pp.1357-1362, 1981.
- M. J. Bastiaans: "Gabor's expansion of a signal into Gaussian elementary signals,"
Proc. IEEE, vol.68, no.4, pp.538-539, 1980.
- G. Battle: "Heisenberg proof of the Balian-Low theorem," Lett. Math. Phys., vol.15, pp.175-177, 1988.
- I. Daubechies: "The wavelet-transform, time-frequency localization and signal analysis," IEEE Trans. Inform. Theory, vol.36, no.5, pp.961-1005, 1990.
- I. Daubechies and A. J. E. M. Janssen: "Two theorems on lattice expansions," IEEE Trans. Inform. Theory, vol.39, no.1, pp.3-6, 1993.
Lecture 14: Continuous Wavelet Transform
- S. Mallat: A Wavelet Tour of Signal Processing, 3rd Ed.,
Academic Press, 2009. Chap. 4, 5.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992.
Chap. 3, 4.
- M. Holschneider: Wavelets: An Analysis Tool, Clarendon Press,
Oxford, 1995. Chap. 1.
Historic papers by Calderón and Grossman & Morlet can be found at:
- A.
P. Calderón: "Intermediate spaces and interpolation, the complex
method," Studia Mathematica, vol.XXIV, pp.113-190, 1964.
- A. Grossmann and J. Morlet: "Decomposition of Hardy functions into square integrable wavelets of constant shape," SIAM J. Math. Anal., vol.15, no.4, pp.723--736, 1984.
Lecture 15: Continuous Wavelet Transform II: Analytic Wavelets
Analytic Signals:
- A. Papoulis: Signal Analysis, McGraw-Hill, 1977. Sec.4-2.
- M. T. Taner, F. Koehler, and R. E. Sheriff: "Complex seismic trace analysis," Geophysics, vol.44, no.6, pp.1041-1064, 1979; See also the errata, Geophysics, vol.44, no.11, p.1896, 1979.
Analytic Wavelets:
- S. Mallat: A Wavelet Tour of Signal Processing, 3rd Ed.,
Academic Press, 2009. Chap. 4.
- M. Holschneider: Wavelets: An Analysis Tool, Clarendon Press,
Oxford, 1995. Chap. 1.
Some historic papers by J. Morlet and collaborators:
- J. Morlet, G. Arens, E. Fourgeau, and D. Glard: "Wave propagation and sampling theory--Part I: Complex signal and scattering in multilayered media," Geophysics, vol.47, no.2, pp.203-221, 1982.
- J. Morlet, G. Arens, E. Fourgeau, and D. Glard: "Wave propagation and sampling theory--Part II: Sampling theory and complex waves," Geophysics, vol.47, no.2, pp.222-236, 1982.
- A. Grossmann and J. Morlet: "Decomposition of Hardy functions into square integrable wavelets of constant shape," SIAM J. Math. Anal., vol.15, no.4, pp.723--736, 1984.
Lecture 16: Discrete Wavelet Transforms; Multiresolution Approximation
For the regular hyperbolic sampling scheme and the frame conditions for
discretizing the continuous wavelet transform, see:
- I. Daubechies: "The wavelet-transform, time-frequency localization and signal analysis," IEEE Trans. Inform. Theory, vol.36, no.5, pp.961-1005, 1990.
- J.-P. Kahane and P.-G. Lemarié-Rieusset: Fourier Series
and Wavelets, Studies in the Development of Modern Mathematcis, Vol.3,
Gordon and Breach Publishers, 1995. Chap. 2 of the Wavelet portion.
The standard references on the multiresolution approximations are:
- S. Mallat: A Wavelet Tour of Signal Processing, 3rd Ed.,
Academic Press, 2009. Chap. 7.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992. Chap. 5.
- J.-P. Kahane and P.-G. Lemarié-Rieusset: Fourier Series
and Wavelets, Studies in the Development of Modern Mathematcis, Vol.3,
Gordon and Breach Publishers, 1995. Chap 3 of the Wavelet portion.
Lecture 17: Scaling Functions; Conjugate Mirror Filters
- S. Mallat: A Wavelet Tour of Signal Processing, 3rd Ed.,
Academic Press, 2009. Chap. 7.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992. Chap. 5.
Lecture 18: Mother Wavelets; Orthonormal Wavelet Basis
An excellent overiew of the wavelet transforms/bases and their impact
to applications, which I distributed in this lecture is:
- I. Daubechies: "Wavelets and Applications," in The Princeton Companion to Mathematics (T. Gower, Ed.), Princeton Univ. Press, 2008, pp.848-862.
2008.
Lecture 19: Orthonormal Wavelet Basis II; Wavelet Packets; Harmonic Analysis on Graphs
For more about the orthonormal wavelet bases, see e.g.,
- S. Mallat: A Wavelet Tour of Signal Processing, 3rd Ed.,
Academic Press, 2009. Chap. 7.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992. Chap. 7.
For the wavelet packets and their dual, i.e., local cosines, see e.g.,
- S. Mallat: A Wavelet Tour of Signal Processing, 3rd Ed.,
Academic Press, 2009. Chap. 8.
Finally, for harmonic analysis on graphs or wavelets on graphs,
see e.g.,
- F. R. K. Chung: Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, no. 92, Amer. Math. Soc., 1997.
Some of the chapters are available from her website.
- Applied and Computational Harmonic Analysis, Special Issue on Diffusion Maps and Wavelets, (D. Donoho and C. Chui, Eds.), vol. 21, no. 1, pp. 1-144, 2006.
Please email
me if you have any comments or questions!
Go
back to Applied & Computational Harmonic Analysis home page