HW4

Problems:
#5.43, 44, 45, 48, 49, 51, 55, 58
#6.10 (Moved to HW5)

Problems: [click here]
Due: Apr 15 (Monday)
Submit: To the TA in the tutorial

Lecture 15 (Mar 25)

Delta function

$$
\mathcal{F}(1)=\delta(y)
$$

$$
\mathcal{F}(\delta)=1
$$

$$
\mathcal{F}(\cos 2\pi x) = \frac{1}{2} [ \delta(y-1)+\delta(y+1)]
$$

Some properties of Fourier Transform

1)
$$

\mathcal{F}(f(ax+b))=\frac{1}{a} e^{\frac{2\pi i by}{a}} \hat{f} \left( \frac{y}{a} \right)
$$
2)
$$

\mathcal{F}(f')=2\pi i y \mathcal{F}(f)
$$
3) Plancherel Identity
$$
\int |f(x)|^2 dx = \int |\hat{f}(y)|^2 dy
$$
4) $\hat{f}(0)=\int f(x) dx=$ are area under the function.

Convolution

$$
f*g(x)=\int_{-\infty}^{\infty} f(x-y) g(y) dy
$$

Properties:
1) Commutative
2) Linear

Convolution Theorem

$\mathcal{F}(f*g)(s)= \hat{f}(s) \cdot \hat{g}(s)$.

Reading Materials

Lecture Notes: p. 82-85, 88-90

Lecture 14 (Mar 22)

Expansions on other intervals

Given a periodic function $f(x)$ on an interval $[-L,L]$, we have
$$
f(x)= \frac{a_0}{2} + \sum_{n=1}^{\infty} \left[ a_n \cos \frac{n\pi x}{L}+ b_n \sin \frac{n\pi x}{L} \right]
$$
where
$$
a_n = \left<f(x),\cos \frac{n\pi x}{L} \right> \, \mbox{ and } \, b_n = \left<f(x),\sin \frac{n\pi x}{L} \right>
$$
and $<f,g>=\frac{1}{L} \int_{-L}^L f(x) g(x) dx$.

Fourier transform

$$
\mathcal{F}(f)(y)= \hat{f}(y) = \int_{-\infty}^{\infty} f(x) e^{-2\pi i xy} dx
$$
and
$$
\mathcal{F}^{-1}(\hat{f}(x)) = f(x) = \int_{-\infty}^{\infty} \hat{f}(y) e^{2\pi i xy} dy \, .
$$

Fourier spectrum

$|\hat{f}(y)|$.

Examples

$$

f(x)=\left\{

\begin{array}{c}

A \mbox{ for $-x_0<x<x_0$} \\

0 \mbox{ otherwise.}

\end{array}

\right.

$$

$$

f(x)=\left\{

\begin{array}{c}

e^{-ax} \mbox{ for $x>0$} \\

0 \mbox{ otherwise.}

\end{array}

\right.

$$

Some difficulties: what are $\mathcal{F}(1)$ and $\mathcal{F}(\cos 2\pi x)$?

Reading Materials

Lecture Notes p.80-82

Lecture 13 (Mar 18)

Fourier Series

Consider
$$
\mathcal{B}=\left\{ \frac{1}{\sqrt{2}} , \cos x, \cos 2x, \cdots, \sin x, \sin 2x , \cdots \right\} \, .
$$

With respect to the inner product
$$
<f,g> = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) g(x) dx \, ,
$$
$\mathcal{B}$ is orthonormal.

Fourier series:
$$
f(x)=\frac{a_0}{2} + \sum_{n=1}^{\infty} ( a_n \cos nx + b_n \sin nx ) \, ,
$$
where
$$
a_0=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) dx \, , \, a_n=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \cos nx dx \, , \, b_n=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \sin nx dx \, .
$$

Example: $f(x)=x$ on $x\in(-\pi,\pi)$ with periodic extension and is normalized. The partial sum of the Fourier series is given by
$$
s_N(x)= 2\sum_{n=1}^N \frac{(-1)^{n+1}\sin nx}{n} \, .
$$

Pointwise convergence

Given $x^*$, $\forall \epsilon>0, \exists N$ such that $n>N$ we have
$$
|s_n(x^*)-f(x^*)|<\epsilon \, .
$$

But, let $x_N=\frac{2N-1}{2N+1} \pi$, we have
$$
s_N(x_N)-f(x_N) > 0.5622 \, .
$$
This implies: $\forall N, \exists x_N$ such that
$$
|s_N(x_N)-f(x_N)| > 8.9\% \mbox{ of the jump.}
$$

Complex form of Fourier Series

$$
f(x)=\sum_{n=-\infty}^{\infty} c_n e^{inx}
$$
where
$c_n=<f(x),e^{inx}>=\frac{1}{2\pi} \int_{-\pi}^{\pi} f(x) e^{-inx} dx$ or $c_n=\frac{a_n-ib_n}{2}$ and $c_{-n}=\frac{a_n+ib_n}{2}$.

Def (Spectrum): $|c_n|$ vs. $n$.

Reading materials

Lecture Notes p.71-80

Midterm (Announcement 2)

Date: Mar 29 (Friday)
Time: 12noon-1pm
Venue: Lecture Room

Materials covered up to, and including, "Why 1-norm minimization promotes sparsity?" from Lecture 12, i.e. Lecture Notes p.69 and HW3.

Project Mid-Report

Mid report due: Apr 14 (Sunday) 1159pm. (3% of your course grade)

Apart from the proposals on this page [click here], you are also encouraged to design your own project. I am very happy to discuss with you on your preference. But please come talk to me by Apr 4 (Thur).

Mid report

Please form a group of 1-3 students.

The requirement for the mid report is no more than three (3) pages in the LaTex/MSWord format.

Your report should contain a clear goal of the project. You can include some background materials on the topic. You should also state some possible reference papers, books, webpage, etc that you are going to use in your work.

You are encouraged to discuss with me by Apr 4 (Thur) to confirm your project so you have around a week to work on the report.

Lecture 12 (Mar 15)

Example on low rank matrix completion.

Why 1-norm minimization promotes sparsity?

Fourier Series

Consider
$$
\mathcal{B}=\left\{ \frac{1}{\sqrt{2}} , \cos x, \cos 2x, \cdots, \sin x, \sin 2x , \cdots \right\} \, .
$$

With respect to the inner product
$$
<f,g> = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) g(x) dx \, ,
$$
$\mathcal{B}$ is orthonormal.

Fourier series:
$$
f(x)=\frac{a_0}{2} + \sum_{n=1}^{\infty} ( a_n \cos nx + b_n \sin nx ) \, ,
$$
where
$$
a_0=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) dx \, , \, a_n=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \cos nx dx \, , \, b_n=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \sin nx dx \, .
$$

Example: $f(x)=x$ on $x\in(-\pi,\pi)$ with periodic extension and is normalized. The partial sum of the Fourier series is given by
$$
s_N(x)= 2\sum_{n=1}^N \frac{(-1)^{n+1}\sin nx}{n} \, .
$$

Reading materials

Lecture Notes: p.67-71