Math 414-501 — Spring 2017

Test 3 Review

General Information

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

Bluebooks. Please bring an 8½×11 bluebook.

Office hours. I will have office hours on Wednesday (4/26/17), 11:10-1:30 and on Thursday (4/27/17), 10:30-12:30 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 on 4/21/17 and 4/24/17. 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 derivations of some of the formulas we have discussed in class.

Topics Covered

Discrete Fourier Transforms

Definition & properties.
  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. $\mathcal S_n$. This is the space of $n$ periodic sequences. Be able to show that the DFT and inverse DFT of an $n$ periodic sequence is an $n$ periodic sequence — i.e, that the DFT and inverse DFT transform $\mathcal S_n$ into itself.
  4. Convolutions and shifts Be able to do prove Theorem 3.4 (HW 7, problems 1 and 2.)
  5. 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.

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.

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." See the class notes for 4/24/17).

Updated 4/25/2017.