Applied & Computational Harmonic Analysis:
Comments, Handouts, and References Page (Spring 2006)
Course: MAT 271
CRN: 93572
Title: Applied & Computational Harmonic Analysis
Class: MW 4:10pm-5:30pm, 1134 Bainer
Instructor: Naoki Saito
Office: 2142 MSB
Phone: 754-2121
Email:saito@math.ucdavis.edu
Office Hours: 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? Basics of the Fourier Transforms
Good references on basic Fourier analysis: - H. Dym & H. McKean:
Fourier Series and Integrals, Academic Press, 1972. Chap. 2.
- G. B. Folland: Fourier Analysis and Its Applications,
Brooks/Cole, 1992. Chap. 7.
- M. A. Pinsky: Introduction to Fourier Analysis and Wavelets,
Brooks/Cole, 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, 2nd Ed., Morgan
Kaufmann Publ., 2000. In particular, Chapters 8 & 9.
Lecture 2: Basics of the Fourier Transforms II, L2 Theory
Details of L2 theory:
- G. B. Folland: Real Analysis, 2nd Ed., Wiley
Interscience, 1999. Chap. 8.
- Pinsky: Chap.2.
- E. M. Stein & G. L. Weiss: Introduction to Fourier
Analysis on Euclidean Spaces, Princeton Univ. Press, 1970. Chap. 1.
Lecture 3: The Heisenberg Uncertainty Principle, Bandlimited
Functions, and Sampling Theorems
Survey on the uncertainty principle (advanced):
- G. B. Folland & A. Sitaram: "The uncertainty principle: A
mathematical survey," Journal of Fourier Analysis and
Applications, vol.3, no.3, pp.207-238, 1999.
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.
Lecture 4: Proof of the Sampling Theorem; Periodization vs
Sampling; Fourier Series
Lecture 5: Smoothness of Functions and Decay Rate of the
Fourier Coefficients; Functions of Bounded Variation
Smoothness Class Hierarchy: - P. J. Davis and P.
Rabinowitz: Methods of Numerical
Integration, Academic Press, 1984, Sec. 1.9.
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.
- M.
Taibleson: "Fourier coefficients of functions of bounded variation," Proc.
Amer. Math. Soc., vol.18, pp.766, 1967.
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: Fourier Series on Intervals; Discrete Fourier
Transform
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!
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, 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.
Lecture 7: Discrete Fourier Transform II; Trigonometric
Interpolation
In addition to the references in Lecture 6, I would also recommend: - Cleve
Moler: Numerical Computing with MATLAB, SIAM, 2004, Chap.8 Fourier
Analysis.
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, 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
- 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 Expansion
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.
We only discussed the discrete version in the class, but KLE 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: KLT vs SVD; KLT vs DCT
Relationship with DCT: - N. Ahmed, T. Natarajan, 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.
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, 2006.
- H. Widom: "Toeplitz matrices," in Studies in Real and Complex
Analysis (I. I. Hirschman, Jr. ed.), MAA Studies in Mathematics,
1965.
HW 3 related info: Ramp Process - Y. Meyer: Oscillating
Patterns in Image Processing and Nonlinear Evolution Equations,
University Lecture Series, vol.22, AMS, 2001, Sec.1.8-1.10.
HW3 related info: 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, 2nd Ed.,
Academic Press, 1999. 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,
pp.961-1005, 1990.
Some historical papers: - D. Gabor: "Theory of
communication," J. IEE (London), vol.93, pp.429-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: Inversion of Windowed Fourier Transform;
Introductory Frame Theory
- S. Mallat: A Wavelet Tour of Signal Processing, 2nd
Ed., Academic Press, 1999. Chap. 4 & 5.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992.
Chap. 3, 4.
- I.
Daubechies: "The wavelet-transform, time-frequency localization and
signal analysis," IEEE Trans. Inform. Theory, vol.36,
pp.961-1005, 1990.
The fascinating book I mentioned in the lecture, containing the
statement on why synthesis is recently getting more important
than analysis, is: - Albert-László Barabási: Linked:
How Everything Is Connected to Everything Else and What It Means for
Business, Science, and Everyday Life, A Plume Book, 2003.
Lectures 14-15: More about Frame Theory; the Balian-Low
Theorem
- S. Mallat: A Wavelet Tour of Signal Processing, 2nd
Ed., Academic Press, 1999. Chap. 5.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992.
Chap. 3, 4.
- K.
Gröchenig: Foundations of Time-Frequency Analysis,
Birkhauser, 2001. Chap's. 5--7.
- O.
Christensen: An Introduction to Frames and Riesz Bases,
Birkhauser, 2002.
- J.-P. Kahan 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 signal expansion and degrees of freedom of a
signal," Proc. IEEE, vol.68, 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,
pp.961-1005, 1990.
- I.
Daubechies and A. J. E. M. Janssen: "Two theorems on lattice
expansions," IEEE Trans. Inform. Theory, vol.39, pp.3-6, 1993.
Lecture 16: Continuous Wavelet Transform
- S. Mallat: A Wavelet Tour of Signal Processing, 2nd Ed.,
Academic Press, 1999. 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.
Lecture 17: Continuous Wavelet Transform II: Analytic Wavelets
Analytic Wavelets:
- S. Mallat: A Wavelet Tour of Signal Processing, 2nd Ed.,
Academic Press, 1999. 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 18: Multiresolution Approximation; Scaling Functions
- S. Mallat: A Wavelet Tour of Signal Processing, 2nd Ed.,
Academic Press, 1999. Chap. 7.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992. Chap.5.
- J.-P. Kahan 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 19: Scaling Functions II; Conjugate Mirror Filters
- S. Mallat: A Wavelet Tour of Signal Processing, 2nd Ed.,
Academic Press, 1999. Chap. 7.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992. Chap.5.
Lecture 20: Mother Wavelets; Orthonormal Wavelet Basis
- S. Mallat: A Wavelet Tour of Signal Processing, 2nd Ed.,
Academic Press, 1999. Chap. 7.
- I. Daubechies: Ten Lectures on Wavelets, SIAM, 1992. Chap.5.
Please email
me if you have any comments or questions!
Go
back to Applied & Computational Harmonic Analysis home page