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.
- 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.
- 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$.
- 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.
- 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$.
- 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.
- 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.