Math 414-501 — Spring 2018

Test 3 Review

General Information

Time and date. Test 3 will be given on Friday, 4/27/18, at 10:20, in our usual classroom.

Bluebooks. Please bring an 8½×11 bluebook.

Office hours. In addition to my usual office hours, I will have extra office hours on Wednesday (4/25/18), 2:30-4 and on Thursday (4/25/18), 2-3:30.

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 and coverage. There will be 4 to 6 questions, some with multiple parts. The test will cover section 2.4 (the sampling theorem), chapter 4 and sections 5.1, 5.2, 5.3.3, 5.3.4, 6.2 and 6.3 in the text. The problems will be similar to ones done for homework, and as examples in class and in the text. Here are links to practice tests: 2001 and 2009. Be aware that these tests cover some material that will not be on the test for this class. Note: this test will involve doing one or two of the theoretical items listed below in bold.

Topics Covered

The Sampling Theorem. Be able to state and prove this theorem, and to define these terms: band-limited function, Nyquist frequency, and Nyquist rate. This theorem is important in the Shannon MRA.

Multiresolution analysis (MRA). You will be asked to define Mallat's multiresolution analysis, including the approximation spaces (V_j's) and $\phi$, the scaling function. Below are some important properties that you should know.

  1. The set $\{2^{j/2}\phi(2^jx-k)\}_{k \in \mathbb Z}$ is an orthonormal basis for $V_j$. The $j=0$ case is the fifth item in the definition of an MRA. The other $j$'s follow from it.

  2. The scaling relation is $\phi(x) = \sum_{k=-\infty}^\infty p_k \phi(2x-k),\ p_k=2\int_{-\infty}^\infty \phi(x)\phi(2x-k)dx$.

  3. The wavelet space $W^{j-1} :=\{w\in V_{j}\ \colon w \perp V_{j-1}\}$. Know that the wavelet $\psi(x)= \sum_{k=-\infty}^\infty (-1)^k p_k \phi(2x-k)$, that $\{2^{(j-1)/2}\psi(2^{(j-1)}x-k)\}_{k \in \mathbb Z}$ is an o.n. basis for $W_{j-1}$, and that $V_j=V_{j-1}\oplus W_{j-1}$, where $V_{j-1}$ is orthogonal to $W_{j-1}$. If the factors of $2^{j/2}$ and $2^{(j-1)/2}$ are dropped, then the bases are just orthogonal.

  4. The previous item implies that that there are two orthogonal bases for $V_j$: (1) $\{\phi(2^jx-k)\}_{k \in \mathbb Z}$ and (2)$\ \{\phi(2^{j-1}x-k)\}_{k \in \mathbb Z}\cup \{\psi(2^{j-1}x-k)\}_{k \in \mathbb Z}$. Thus, $f(x)\in V_j$ can be represented in two ways: \[ f(x)=\sum_{k=-\infty}^\infty a^j_k\phi(2^j x-k) \ \text{and } f(x)=\sum_{k=-\infty}^\infty a^{j-1}_k\phi(2^{j-1} x-k)+\sum_{k=-\infty}^\infty b^{j-1}_k \psi(2^{j-1}x-k), \] where $a^j_k=2^j \int_{-\infty}^\infty f(x)\phi(2^j x-k)dx$, $\ a^{j-1}_k$ is just the previous formula with $j$ replaced by $j-1$, and $b^{j-1}_k =2^{j-1} \int_{-\infty}^\infty f(x)\psi(2^{j-1} x-k)dx$.

  5. Decomposition formulas give $a^{j-1}$ and $b^{j-1}$ in terms of $a^j$; the reconstruction formulas give $a^j$ in terms of $a^{j-1}$ and $b^{j-1}$. See equation (5.12) for decomposition, and equation (5.13) for reconstruction.

  6. Filter diagrams can be used to describe the decomposition and reconstruction formulas. There are four filters involved — high pass and low pass decomposition filters, $h$, $\ell$, and high pass low pass Reconstruction filters, $\tilde h, \tilde \ell$. (These filters will be provided on the test.) See equations (5.17) and (5.23), and the filter diagrams in Figures 5.6 and 5.12.

Scaling relation. Be able to show that the scaling relation in (2) above holds, given the o.n. basis for $j=1$ from (1). (Theorem 5.6.)

Filters. You will be given the high-pass and low-pass decomposition and reconstruction filters. Know how to implement both decomposition and reconstruction algorithms in terms of filter diagrams. (See Figures 5.6 and 5.12.) Be able to use the filter diagram to find the decomposition formulas.

Fourier transform criteria for an MRA. Be able to find the Fourier transform of the scaling function $\phi$ and to state the FT of $\psi$ (Theorem 5.19) in terms of $P(z)$. Be able to state Theorem 5.23, which states conditions sufficient for the $p_k$'s to give an MRA.

Haar and Shannon MRAs. 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 down sampling and up sampling are, and finally be able to use filter diagrams to describe the decomposition and reconstruction algorithms. Be able to do problems similar to those for the Haar MRA given in Assignments 7 and 8. For the Shannon MRA, be able to define the $V_j$'s and the scaling function. Be able to use the Sampling Theorem to find the $p_k$'s.

Processing a signal. Be able to state the steps in processing a signal.

Daubechies' wavelets and vanishing moments. Know how the Daubechies wavelets are classified using $N$, the largest power of $z+1$ that divides $P(z)$, and that $N$ is the number of vanishing moments of the Daubechies wavelet. For $N=2$, be able to show that $f(x)=Ax+B$ is "reproduced" — i.e., bjk=0 for such $f$. Using this, be able to explain how a wavelet analysis can be used in singularity detection and data compression.

Updated 4/24/2018.