Math 414-501 — Final Exam Review

General Information

The final exam will be given in our usual classroom on Tuesday, 5/6/14. Please bring an 8½×11 bluebook. I will have extra office hours this week; I'll announce the times later. The test will cover material from chapter 4, chapter 5, sections 5.1, 5.2, 5.3 (Theorem 5.19, eqns. 5.29 and 5.30, and Theorem 5.23 - part of the theorem is missing; see below), sections 6.2 and 6.3. There will be no direct questions from chapters 1-3. However, you will need to know it insofar as it is used in conjunction with the material on wavelets.

Calculators. You may use calculators to do arithmetic, although you will not need them. You may not use any calculator that has the capability of doing linear algebra or storing programs or other material.

Other devices. You may not use cell phones, computers, or any other device capable of storing, sending, or receiving information.

Structure. There will be 6 to 8 questions, some with multiple parts. The problems will be similar to ones done for homework, and as examples in class and in the text.

Topics Covered

Haar wavelets. Know the Haar scaling function, wavelet, approximation spaces (V's), and wavelet spaces (W's). Using the Haar wavelet and scaling function, be able to carry out simple decomposition and reconstruction algorithms. Know what the various high pass and low pass filters associated with these algorithms are, what downsampling and upsampling are, and finally be able to use filter diagrams to describe the decomposition and reconstruction algorithms.

Multiresolution analysis (MRA). You will be asked to define Mallat's multiresolution analysis, including the approximation spaces (V's), the scaling relation, the wavelet spaces (W's), and the wavelet itself. Know the decomposition and reconstruction formulas, high-pass and low-pass decomposition and reconstruction filters, downsampling and upsampling. Be able to discuss the details of the multiresolution analysis in the Haar case or for the Shannon MRA (exercise 8 in § 5.4). Know how to implement both decomposition and reconstruction algorithms. In particular, be able to show that the top level coefficients, which are used in the initialization step, have the approximate form $a^j_k \approx m \,f(2^{-j}k)$, where $m = \int_{-\infty}^\infty \phi(x)dx$. (Theorem 5.12).since scaling functions are usually normalized so that $m=\int_{-\infty}^\infty \phi(x)dx= 1$, the previous formula becomes $a^j_k \approx f(2^{-j}k)$,

Fourier transform criteria for an MRA. Be able to find the Fourier transformed (i.e., frequency space) form of the scaling relation (Theorem 5.19). Be able to outline how the scaling function and the wavelet are derived from the function P(z) that satisfies the conditions in Theorem 5.23:

Theorem 5.23 Suppose $P(z) := \frac12 \sum_{k\in \mathbb Z}p_kz^k$ is a polynomial that satisfies the following conditions: Then $\hat\phi(\xi)=\frac{1}{\sqrt{2\pi}}\Pi_{k=1}^\infty P(e^{-\xi i/2^k})$ is the Fourier transform of a scaling function.

Vanishing moments. The $k^{th}$ moment of a wavelet $\psi$ is defined to $m_k=\int_{-\infty}^\infty x^k\psi(x)dx$. Know what the significance of the first $N$ moments, $m_0,\ldots,m_{N-1}$, vanishing is: What effect does it have the magnitude of the $b^j_k $s? What happens for a polynomial signal of degree $N-1$ or less? How does it help in singularity detection or data compression? Know that the first $N$ moments vanish if and only if $P(z) = \big(\frac{1+z}{2}\big)^N \tilde P(z)$.

Daubechies' wavelets. Know how the Daubechies wavelets are classified using N, the largest power of z+1 that divides P(z), and also know how N relates to the number of vanishing moments of the Daubechies wavelet. Be able to explain various ways of handling the problem of overspill; see section 6.3.

Updated 4/28/2014.