Math 414-501 — Spring 2019

Test 3 Review

General Information

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

Bluebooks. Please bring an 8½×11 bluebook.

Office hours. I will have office hours on Wednesday (4/24/19), 1:40-3:30, and on Thursday (4/25/19), 1-3 pm.

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 calculus, or of 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 sections 3.1-3.1.4, 3.2.1 (discrete-time sequences, filters, convolutions and the convolution theorem), chapter 4, and the material from chapter 5 covered in class. 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, 2009 and 2012. Be aware that these tests cover some material that will not be on the test for this class. Note: this test will involve derivations of some of the formulas we have discussed in class.

Topics Covered

Discrete Fourier Transforms and Discrete Signals

Definition & properties of the DFT.
  1. DFT. Be able state the formulas for both the DFT and inverse DFT.
  2. Approximation to Fourier transforms. Know how to approximate a Fourier transform using the DFT.
  3. Convolutions and shifts Be able to do prove Theorem 3.4 (See HW 8, problems 1 and 2.)
  4. FFT. Know what the fast Fourier transform (FFT) algorithm for computing the DFT is. Be able to compare the number of multiplications needed to compute the DFT vs. the number for the FFT.

Discrete Signals
  1. Discrete filters, convolutions, and the Z-transform.

Haar Wavelet Analysis

Haar MRA. Be able to state the Haar scaling function, wavelet, approximation spaces ($V_j$'s), and wavelet spaces ($W_j$'s).
  1. Using the Haar wavelet and scaling function, be able to carry out simple decomposition and reconstruction algorithms.
  2. Know what the various high pass and low pass filters associated with these algorithms are, what down sampling and up sampling are, and be able to use these to do problems similar to those in HW 9 and HW 10.

Multiresolution analysis (MRA)

Multiresolution analysis (MRA). Be able to define Mallat's multiresolution analysis.

  1. Be able to derive the scaling relation $\phi(x)=\sum_{k=-1}^\infty p_k \phi(2^jx-k)$.
  2. Given the scaling relation, be able to show that the wavelet $\psi(x) = \sum_{k=-\infty}^\infty (-1)^k p_{1-k} \phi(2^jx-k)$
  3. Be able to discuss the details of the Haar MRA case the Shannon MRA (exercise 8 in § 5.4; be sure to know the Whittaker-Shannon Sampling Theorem, §2.4.)
  4. Be able to derive the decomposition formulas. Be able to state the reconstruction formulas. Know the high-pass and low-pass decomposition and reconstruction filters, down sampling and up sampling. Know how to implement both decomposition and reconstruction algorithms in terms of filters.

Processing a signal. Be able to state the steps in processing a signal. In the initialization step, be able to briefly explain why, for the top level $j$, $a^j_k \approx \,f(2^{-j}k)$, where we will use $m = \int_{-\infty}^\infty \phi(x)dx=1$. (This is the "wavelet crime.").

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) in terms of $P(z)$. Be able to state Theorem 5.23.

Updated 4/22/2019.