Lectures 23 and 24 (May 6)

Constrained Optimization: Lagrange multiplier: $\min_u I(u)$ subject to $J(u)=0$ becomes $\min_{u,\lambda} I(u)+\lambda J(u)$.

A simple model for image denoising

Additive noise model: $f=u+n$, where $f$ is the observed image, $u$ is an unknown clean image and $n$ is the noise following $N(0,\sigma^2)$.

$$
\min \int |\nabla u|^2
$$
such that $\int n^2 = \int (f-u)^2 =\sigma^2$.

We introduce a Lagrange multiplier and minimize the following functional
$$
\min \int |\nabla u|^2 + \lambda (f-u)^2 \, .
$$

The Euler-Lagrange equation is given by
$$
-\Delta u + \lambda (f-u) = 0 \, .
$$

Solving it using Fourier transform, we have
$$
u= \mathcal{F}^{-1} \left( \frac{1}{1+\frac{4\pi^2}{\lambda} (p^2+q^2)} \hat{f}_{p,q} \right) \, .
$$
And this is the Butterworth low pass filter.

Rudin-Osher-Fatemi (ROF)

$$

\min \int |\nabla u| + \lambda (f-u)^2 \, .

$$

The Euler-Lagrange equation is given by

$$

-\nabla \cdot \left( \frac{\nabla u}{|\nabla u|} \right) + 2 \lambda (f-u) = 0 \, .

$$

Some properties of ROF:

1) Comparing with the diffusion equation

$$

\frac{\partial u}{\partial t} = \nabla \cdot \left( a(x) \nabla u \right) \, .

$$

For homogeneous region, $|\nabla u| \sim 0$ and so $a(x) \gg 1$, which gives fast diffusion.

Near edge, $|\nabla u| \gg 1$ and so $a(x) \sim 0$, which gives small diffusion.

2) Decide $\lambda$ in the original paper

$$

\lambda= \frac{1}{2\sigma^2} \int \frac{\nabla u \cdot \nabla f}{|\nabla u|} - |\nabla u| \, .

$$

3) Coarea formula

$$

\int \| \nabla 1_{\Omega} \|_2 = \mbox{ arclength of $\partial \Omega$} \, .

$$

Therefore, if $f=1_{\mathcal{B}_r}$, the minimizer to the ROF is

$$

u= c \, 1_{\mathcal{B}_r} = \max(0,1-\frac{1}{\lambda r}) \, 1_{\mathcal{B}_r} \, .

$$

This implies some part of the signal will always be regarded as noise.

p.127: the derivation on showing that the diffusion is along the tangential direction of the contours.

TV-L1 (BV-L1) Model

$$

E(u)= \int \| \nabla u \| + \lambda |f-u| \, .

$$

If $f=1_{\mathcal{B}_r(0,0)}$, then the minimizer to the TV-L1 model is

$u=f$ if $\lambda r>2$ and $u=0$ if $\lambda r<2$.

Reading Materials

MATLAB Demo: [click here]

PPT: [click here]

Lecture Notes: p.120-127

Lecture 21 and 22 (Apr 29)

Calculus of variation

Functional: I(y): function $\rightarrow \mathbb{R}$.

Example: Brachistochrone Problem:
$$
I(y)=\int_a^b \sqrt{\frac{1+(y')^2}{2gy}} dx \, .
$$

Euler-Lagrange equation

first order optimality condition. Necessary but not sufficient.

Euler's solution: let $N=\frac{\partial f}{\partial y}$ and $P=\frac{\partial f}{\partial y'}$,
$$
N- \frac{d}{dx} P =0 \, .
$$

Gradient Descent

$$
\min_x f(x)
$$
where $f:\mathbb{R} \rightarrow \mathbb{R}$.

Direct approach: Solve $f'(x)=0$ for $x$.

Iterative approach:
$$
x_{n+1}=x_n-\epsilon f'(x_n)
$$
for some initial guess $x_0$ and some small $\epsilon>0$.

Time-dependent approach: artificial time $t$,
$$
\frac{x_{n+1}-x_n}{\epsilon} = -f'(x_n) \, .
$$
Taking $\epsilon \rightarrow 0$, we have
$$
\frac{d}{dt} x(t) = -f'(x(t)) \, ,
$$
with the initial condition $x(t=0)=x_0$. The steady state solution will correspond to a local minimum.

$$
\frac{d}{dt} f(x(t)) = \frac{df}{dx} \cdot \frac{dx}{dt} = f' \cdot (-f') = -(f')^2 \le 0 \, .
$$

Gradient Descent for Functional

$$
\min_y I(y)
$$
for a functional $I$. We introduce an artificial time variable and solve
$$
\frac{\partial y}{\partial t} = - \nabla_y I
$$
with the initial condition $y(x,0)=y_0(x)$. The steady state solution solves $\nabla_y I =0$.

Reading Materials

Lecture Notes: p.110-116

Lecture 20 (Apr 26)

Deconvolution

$g=h*f$, given both $g$ and $h$, want to determine $f$.

If only $g$ is given, we have a blind deconvolution problem.

$$
f=\mathcal{F}^{-1}\left[ \frac{\mathcal{F}(g)}{\mathcal{F}(h)} \right] \, .
$$

If there is noise, $g=h*f+n$, then
$$
f=\mathcal{F}^{-1}\left[ \frac{\mathcal{F}(g)}{\mathcal{F}(h)} \right]
- \mathcal{F}^{-1}\left[ \frac{\mathcal{F}(n)}{\mathcal{F}(h)} \right]
\, .
$$
Problems:
1. $n$ is an unknown;
2. $|\hat{h}_{p,q}| \sim 0$ will amplify the effect from the error term.

Optimization problem

Given $h$ (and so the matrix $H$) and $g$, want to determine $f$ such that
(1) $Hf=g$;
(2) $\min_f \|Hf-g\|_2^2$.

A circulant matrix $H$ can be diagonalized by Fourier transform, i.e. $H=WDW^{-1}$ where $W$ is the Fourier matrix. So $WDW^{-1} f =g$ and we also have $f=WD^{-1}W^{-1} g$, i.e. we determine $f$ by
1. compute the Fourier transform of $g$;
2. divide the Fourier coefficients by the Fourier coefficient of $h$;
3. compute the inverse Fourier transform.

Some matrix operations:
1) $\nabla_x (a^T x)=a$;
2) $\nabla_x (x^T A^T A x)=2 A^T A x$.

The minimizer to the minimization problem $\min_f \|Hf-g\|_2^2$ is given by
$$
f = (H^* H)^{-1} H^* g \, .
$$

Constrained optimization

$$
\min_x f(x)
$$
subject to $g(x)=0$.

Or, using a Lagrange multiplier to obtain an unconstrained optimization problem:
$$
\min_{x,\lambda} f(x)+\lambda g(x) \, .
$$

Constrained optimization formulation for deconvolution with noise:
$$
\min_f \|Q f\|_2^2
$$
subject to $\|Hf-g\|_2^2=\|n\|_2^2$, for some linear location-invariant operator $Q$, i.e. both $H$ and $Q$ can be diagonalized by the Fourier transform, $H=WDW^{-1}$ and $Q=WAW^{-1}$. The minimizer to the constrained problem can be solved by introducing a Lagrange multiplier. The solution is
$$
f=W\left(D^T D+\frac{1}{\lambda} A^T A \right)^{-1} D^T W^{-1} g \, .
$$

In the component form, we have
$$
f = \mathcal{F}^{-1} \left( \frac{d_i^*}{|d_i|^2 + \frac{1}{\lambda} |a_i|^2} \hat{g}_i \right) \, ,
$$
where $\hat{g}=\mathcal{F}(g)$.

Limitation

1) minimization w.r.t. $\lambda$: eye-norm, i.e. try various $\lambda$ and pick the best solution to human;
2) What is $Q$? For example, $Qf=\nabla^2 f$.

Reading materials

Lecture note: p.100-104

HW6

Problems:
#5.91, 94, 97, 100

Problems: [click here]
Due: May 9 (Thursday)
Submit: To the TA 

Project Final Report

Due: May 9 (Thursday) 1159pm

The requirement for the final report is no more than 
(1) eight (8) pages for individual project,
(2) ten (10) pages for group of 2 students,
(3) twelve (12) pages for group of 3 students.

Your project report should contain some background on the topic, the research methodology and your findings with enough supports. It will be graded based on, but not limited to, the following criteria (max 3% each)
1) accuracy;
2) execution;
3) presentation;
4) creativeness.

Any evidence of word-for-word copying from books or webpage will result in a lowered grade. You should research ideas for your group in the library and on the world-wide-web. Your paper should reference papers, books, etc. that you use in your work. 

Please email me a zip file of the final report and any code developed.

Lecture 19 (Apr 15)

Image Denoising

Ideal low pass filter:

$$

\hat{h}_{p,q}= \left\{

\begin{array}{cc}

1 & \mbox{ if $D(p,q)\le D_0$} \\

0 & \mbox{ otherwise.}

\end{array}

\right.

$$

Butterworth low pass filter

$$

\hat{h}_{p,q}=\frac{1}{1+[D(p,q)/D_0]^{2n}} \, .

$$

Gaussian low pass filter

$$

\hat{h}_{p,q}=e^{-D(p,q)^2}{2\sigma^2} \, .

$$

Image Edge Detection

Ideal high pass filter:

$$

\hat{h}_{p,q}= \left\{

\begin{array}{cc}

0 & \mbox{ if $D(p,q)\le D_0$} \\

1 & \mbox{ otherwise.}

\end{array}

\right.

$$

Butterworth high pass filter

$$

\hat{h}_{p,q}=1-\frac{1}{1+[D(p,q)/D_0]^{2n}}=\frac{1}{1+[D_0/D(p,q)]^{2n}} \, .

$$

Gaussian low pass filter

$$

\hat{h}_{p,q}=1-e^{-D(p,q)^2/(2\sigma^2)} \, .

$$

Deconvolution

$g=h*f$, given both $g$ and $h$, want to determine $f$.

If only $g$ is given, we have a blind deconvolution problem.

$$
f=\mathcal{F}^{-1}\left[ \frac{\mathcal{F}(g)}{\mathcal{F}(h)} \right] \, .
$$

Reading materials

MATLAB demo files for the ideal low pass filter: [Driver.m] [ideal_low.m]
Lecture notes: p.94-100

Lecture 18 (Apr 12)

Two dimensional generalizations

1) Fourier Transform
$$
f(x,y)=\int \int \hat{f}(u,v) e^{i2\pi(ux+vy)} du dv \\
\hat{f}(u,v)=\int \int f(x,y) e^{-i2\pi(ux+vy)} dx dy \, .
$$
2) Discrete Fourier Transform
$$
f_{m,n}= \frac{1}{MN} \sum_{p=0}^{M-1} \sum_{q=0}^{N-1} \hat{f}_{p,q} e^{i 2\pi \left( \frac{pm}{M}+\frac{qn}{N} \right)} \\
\hat{f}_{p,q}=\sum_{m=0}^{M-1} \sum_{n=0}^{N-1} f_{m,n} e^{-i 2\pi \left( \frac{pm}{M}+\frac{qn}{N} \right)} \, .
$$

Some properties

1) Periodicity:
$$
\hat{f}_{p,q}=\hat{f}_{p+k_1 M,q}=\hat{f}_{p,q+k_2 N}=\hat{f}_{p+k_1 M,q+k_2 N}
$$
for any integer $k_1$ and $k_2$.
2) Translation:
$$
\mathcal{F} \left[
f_{m,n} e^{i 2\pi \left( \frac{p^*m}{M}+\frac{q^*n}{N} \right)} \right] = \hat{f}_{p-p^*,q-q^*}
$$
3) From (2), take $p^*=M/2$ and $q^*=N/2$, we have
$$
\mathcal{F} \left[
f_{m,n} (-1)^{m+n} \right] = \hat{f}_{p-M/2,q-N/2} \, .
$$

Image Enhancement

Design $\hat{h}$ such that $\tilde{f}=\mathcal{F}^{-1}(\hat{h} \cdot \hat{g})$ achieves some properties.

Reading Materials:

Lecture Notes: p.94

HW5

Problems:
#5.60, 61, 63, 67, 75
#6.10 [Driver_FFT1.m] [Driver_FFT2.m], 11 (Use the expressions in Sec 3.5 and 3.6) [Fig4.11(a)]

Problems: [click here]
Due: May 3 (Friday)
Submit: To the TA in the tutorial

Lecture 17 (Apr 8)

Discrete Fourier Transform

$$

\hat{f}_n = \sum_{m=0}^{N-1} f_m e^{-2\pi i mn/N}

$$

Inverse Discrete Fourier Transform

$$
f_m = \frac{1}{N} \sum_{n=0}^{N-1} \hat{f}_n e^{2\pi i mn/N}
$$

Fourier Matrix: $F_N=[\omega^{mn}]$ where $\omega=e^{-2\pi i/N}$.

The inverse of the Fourier matrix: $F_N^{-1}=\frac{1}{N} \bar{F}_N$.

Fast Fourier Transform

Reading Materials

Lecture Notes: p.92-94

Lecture 16 (Apr 1)

Convolution Theorem

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

Discrete Fourier Transform

$$
\hat{f}_n = \sum_{m=0}^{N-1} f_m e^{-2\pi i mn/N}
$$

Inverse Discrete Fourier Transform

$$
f_m = \frac{1}{N} \sum_{n=0}^{N-1} \hat{f}_n e^{2\pi i mn/N}
$$

Fourier Matrix: $F_N=[\omega^{mn}]$ where $\omega=e^{-2\pi i/N}$.

The inverse of the Fourier matrix: $F_N^{-1}=\frac{1}{N} \bar{F}_N$.

Reading Materials

Lecture Notes: p.90-92

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

Lecture 10/11 (Mar 11)

Thm (Error in the low rank approximation): For any $\nu$ with $0\le \nu \le r=$rank$(A)$, let
$$
A_{\nu} = \sum_{j=1}^{\nu} \sigma_j \mathbf{u}_j \mathbf{v}_j^* \, .
$$
Then
\begin{eqnarray*}
\|A-A_{\nu}\|_2 &=& \mbox{inf}_{B\in \mathbb{R}^{M\times N}, \mbox{rank}(B)\le \nu} \|A-B\|_2 = \sigma_{\nu+1} \, , \\
\|A-A_{\nu}\|_F &=& \mbox{inf}_{B\in \mathbb{R}^{M\times N}, \mbox{rank}(B)\le \nu} \|A-B\|_F = \sqrt{\sigma_{\nu+1}+\cdots+\sigma_r^2} \, .
\end{eqnarray*}

Texture Image Inpainting using low rank matrix completion

Netflix problem: predict user rating for movies.

Reading materials

Lecture Notes: p.59-67

Midterm

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

Materials covered up to, and including, lecture on Mar 22 (Friday).

Lecture 9 (Mar 8)

Def ($N$ singular values of $A$): length of the $N$ principal semiaxes of $AS$, i.e. $\sigma_1, \sigma_2, \cdots, \sigma_N$ such that $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_N >0$.

Def ($N$ left singular vectors of $A$): $\{ u_1, u_2, \cdots, u_N \}$ orthonormal, principal semiaxes directions.

Def ($N$ right singular vectors of $A$): $\{ v_1, v_2, \cdots, v_N \}$, preimage of $\sigma_i u_i$. It turns out these vectors are orthonormal.

Reduced SVD:
$$
A=\hat{U} \hat{\Sigma} V^*
$$
where $\hat{U}\in\mathbb{R}^{M\times N}$, $\hat{\Sigma}\in\mathbb{R}^{N\times N}$ and $V\in\mathbb{R}^{N\times N}$.

Full SVD

$$
A=U \Sigma V^*
$$
where $U\in\mathbb{R}^{M\times M}$, $\Sigma\in\mathbb{R}^{M\times N}$ and $V\in\mathbb{R}^{N\times N}$.

Properties:
1. $v_i$: eigenvectors of $A^*A$.
2. $u_i$: eigenvectors of $AA^*$.
3. Nonzero singular values are the square roots of the nonzero eigenvalues of $A^*A$ or $AA^*$.

4. Rank$(A)=r=$ the number of nonzero singular values.
5. Range$(A)=$span$(u_1,u_2,\cdots,u_r)$.
6. Null$(A)=$span$(v_{r+1},v_{r+2},\cdots,v_N)$.
7. $A$ is the sum of $r$ rank-one matrices,
$$
A=\sum_{i=1}^r \sigma_i u_i v_i^* \, .
$$

Low rank approximation of $A$

For any $\nu$ such that $0\le \nu \le r$, define
$$
A_{\nu}=\sum_{i=1}^{\nu} \sigma_i u_i v_i^*
$$
is an rank-$\nu$ approximation of $A$.

Image Compression using SVD

Vector norm

A function $\| \cdot \|: \mathbb{R}^m \rightarrow \mathbb{R}$ such that
(1) $\|x\| \ge 0$, $\| x\|=0$ only if $x=0$;
(2) $\|x+y\| \ge \|x\| + \|y\|$;
(3) $\|\alpha x\| = |\alpha| \cdot \|x\|$.

Examples: $\|x\|_1$, $\|x\|_2$, $\|x\|_p$, $\|x\|_{\infty}$.

Matrix norm induced by vector norm

Def: $\|A\|$: the smallest $C\in \mathbb{R}$ such that
$$
\|A x\| \le C \|x\|
$$
for all $x\in \mathbb{R}^m$. Or,
$$
\|A\| = \mbox{sup}_{x\in \mathbb{R}^m, x\ne 0} \frac{ \|Ax\|}{\|x\|} = \mbox{sup}_{\|x\|=1, x \in \mathbb{R}^m} \|Ax\| \, .
$$

Reading materials

Lecture notes: p.56-60.

HW3

Problems:
#5.29,35,39,40,41
#6.5[the circuit board image: click here],6,7[Fig 5.26(a)],8

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

Lecture 8 (Mar 4)

Nonlinear Transforms

Denoising: Median filter.

Two different norms for the gradient in two dimensions:
$$
\|\nabla f\|_1 = \left| \frac{\partial f}{\partial x} \right| + \left| \frac{\partial f}{\partial y} \right| \\

\|\nabla f\|_2 = \left[ \left( \frac{\partial f}{\partial x} \right)^2 + \left(\frac{\partial f}{\partial y} \right)^2 \right]^{\frac{1}{2}}
$$

Eigenvalue Decomposition (EVD)

If $A$ is not square, there is no EVD.

Even if it's square, there is no guarantee that it has a complete set of e-vectors.

Singular Value Decomposition (SVD)

Geometrical observation: The image of the unit sphere under any $M\times N$ matrix is a hyperellipse.

Assume $A\in \mathbb{R}^{M\times N}$ is full rank, $M\ge N$.

Def ($N$ singular values of $A$): length of the $N$ principal semiaxes of $AS$, i.e. $\sigma_1, \sigma_2, \cdots, \sigma_N$ such that $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_N >0$.

Def ($N$ left singular vectors of $A$): $\{ u_1, u_2, \cdots, u_N \}$ orthonormal, principal semiaxes directions.

Def ($N$ right singular vectors of $A$): $\{ v_1, v_2, \cdots, v_N \}$, preimage of $\sigma_i u_i$. It turns out these vectors are orthonormal.

Reduced SVD:

$$

A=\hat{U} \hat{\Sigma} V^*

$$

where $\hat{U}\in\mathbb{R}^{M\times N}$, $\hat{\Sigma}\in\mathbb{R}^{N\times N}$ and $V\in\mathbb{R}^{N\times N}$.

Reading materials

Lecture Notes: pp.50-57

Lecture 7 (Feb 22)

Matrix representation of a linear transformation using the elementary basis of $\mathbb{R}^{M\times N}$. Compact representation of $w(s,t)$.

Box filter as an example. $TV(w * g)\le TV(g)$.

Edge detection
$$
g(x,y)=f(x,y)+c \Delta f(x,y) \, ,
$$
with $c<0$.

Reading materials

Lecture Notes: p.45-49.

HW2

Problems:
#5.16. 18, 21, 22, 23, 26
#6.1, 2 [Fig2.21(a)]

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

Lecture 5+6 (Feb 18)

Normalized histogram

$h(r_i)=n_i$ represents the number of pixels in the image with intensity $r_i$. $p(r_i)=n_i/MN$ represents the percentage of pixels with the intensity $r_i$ such that $\sum_{i} p(i)=1$.

Histogram equalization

Given the normalized histogram $p_r(r_i)$, want to determine a transformation $s_i=T(r_i)$ for $i=0,1,\cdots,L-1$ such that $p_s(s_i)$ follows the uniform distribution
$$
\Rightarrow s=T(r)=(L-1) \int_0^r p_r(w) dw \, .
$$
In practice where image intensity is an integer, we have
$$
s_i=\mbox{round}\left[ (L-1) \sum_{j=0}^{i} p_r(r_i) \right] \, .
$$

Additive noise model

$g(x,y)=f(x,y)+n(x,y)$ where $f$ is the unknown clean image, $g(x,y)$ is the observed image and $n(x,y)$ is the noise. We assume $n(x,y)$ is a random variable which follows some distribution.

Gaussian noise, uniform noise, salt-and-pepper noise.

Filtering

Convolution
$$
g(x,y)= \sum_s \sum_t w(s,t) f(x-s,y-t) \, .
$$

Properties:
(i) Linear;
(ii) Convolution is commutative (ignoring the boundary effect).

For most image applications, we assume $w(s,t)$ is compact (only non-zero in a small neighborhood of $(x,y)$) and is symmetric.

Matrix representation of a linear transformation using the elementary basis of $\mathbb{R}^{M\times N}$. Compact representation of $w(s,t)$.

Reading Materials

Lecture notes: p.36-45

Slides: [click here]

Lecture 4 (Feb 15)

Relationship to image inpainting
Taking the mean, mode and median of the neighboring intensities:
$E_2(g) =  \sum_{i=1}^N \left| f_i-g \right|^2$, $E_0(g) =  \sum_{i=1}^N \left| f_i-g \right|^0$ and $E_1(g) =  \sum_{i=1}^N \left| f_i-g \right|^1$.

Intensity transformation [$s=T(r)$]: most are application/image dependent.

Reading Materials

Lecture notes: p.31-35

Slides: [click here]

Lecture 3 (Feb 11)

Image Interpolation

Properties of the piecewise linear interpolation:
1. Will not create new global extrema, i.e. $\max_{x\in[x_1,x_M]} p(x) = \max_i f_i$ and  $\min_{x\in[x_1,x_M]} p(x) = \min_i f_i$.
2. $TV(\mathbf{g})=TV(\mathbf{f})$ where $TV(\cdot)$ is the total variation of the signal.
3. It is a linear transformation from $\mathbb{R}^M$ to $\mathbb{R}^{2M-1}$.

Two dimensional (image) interpolation: bilinear interpolation.

Relationship to image inpainting
Taking the mean, mode and median of the neighboring intensities:
$E_2(g) =  \sum_{i=1}^N \left| f_i-g \right|^2$, $E_0(g) =  \sum_{i=1}^N \left| f_i-g \right|^0$ and $E_1(g) =  \sum_{i=1}^N \left| f_i-g \right|^1$.

Reading materials

Lecture notes: p.29-31

HW1

Problems:
#5.9, 10, 11, 14, 15

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

Lecture 2 (Feb 8)

Problems about the simple imaging model

Sampling: $\Omega \Rightarrow \Omega'=\{(x,y),x=1,2,\cdots,M, y=1,2,\cdots,N\}$.

Quantization: $[0,L-1] \Rightarrow \{0,1,2,\cdots,L-1\}$. MATLAB data type: uint8 and uint16.

Image interpolation

Given a signal $(x_i,f(x_i))$ for $i=1,2,\cdots,M$, we want to determine an approximation to $f(x^*)$ for $x^* \ne x_i$. Using
(i) High order polynomial interpolation: $p(x) \in P^{M-1}$ such that $p(x_i)=f(x_i) \Rightarrow$ one needs to invert a BIG matrix. This can be partially fixed by better basis for interpolation, such as Lagrange Interpolating Polynomials or Newton's Divided Difference.
(ii) Piecewise polynomial interpolation: determine $p_i(x) \in P^N$ for some $N \ll M-1$ such that the polynomial defined only piecewisely for $x \in [x_i,x_{i+1}]$ for $i=1,\cdots,M-1$. Then
$$
p(x) = \left\{
\begin{array}{cc}
p_1(x) & \mbox{ if $x\in[x_1,x_2]$} \\
p_2(x) & \mbox{ if $x\in[x_2,x_3]$} \\
\vdots & \\
p_{M-1}(x) & \mbox{ if $x\in[x_{M-1},x_M]$.}
\end{array}
\right.
$$
In particular, if $N=1$, the interpolation is called a piecewise linear interpolation.

Some properties of the piecewise linear interpolation

Properties of the piecewise linear interpolation:
1. Will not create new global extrema, i.e. $\max_{x\in[x_1,x_M]} p(x) = \max_i f_i$ and  $\min_{x\in[x_1,x_M]} p(x) = \min_i f_i$.
2. $TV(\mathbf{g})=TV(\mathbf{f})$ where $TV(\cdot)$ is the total variation of the signal.
3. It is a linear transformation from $\mathbb{R}^M$ to $\mathbb{R}^{2M-1}$.

Reading materials

Lecture notes: p.21-22,25-29
Presentation file: [click here]

Lecture 1 (Feb 1)

Overview

Introduction

A simple imaging model.
$$
f: \Omega \rightarrow [0,L]
$$
where $\Omega$ is a bounded domain in $\mathbb{R}^2$.

However, such a simple model has two limitations:
(1) Sampling;
(2) Quantization.

Reading materials

Lecture notes: p.20-21
Presentation file: [click here]

Lecture Hours

Week 1		1-Feb	Lecture Hours	Tutorial Hours
		L: Tim	1.5	0
Week 1	4-Feb	8-Feb
	T: Cancel
	L: Cancel	L: Tim	1.5	0
Week 2	11-Feb	15-Feb
	T:Alan
	L: Tim	L: Tim	3	1
Week 3	18-Feb	22-Feb
	T: Tim
	L: Tim	L: Tim	4	0
Week 4	25-Feb	1-Mar
	T: Alan
	L: Alan	L: Alan	0	4
Week 5	4-Mar	8-Mar
	T: Alan
	L: Tim	L: Tim	3	1
Week 6	11-Mar	15-Mar
	T: Tim
	L: Tim	L: Tim	4	0
Week 7	18-Mar	22-Mar
	T: Alan
	L: Tim	L: Tim	3	1
Week 8	25-Mar	29-Mar
	T: Alan
	L: Tim	L: Tim	3	1
Week 9	1-Apr
	T: Tim
	L: Tim		2.5	0
Week 10	8-Apr	12-Apr
	T: Alan
	L: Tim	L: Tim	3	1
Week 11	15-Apr
	T: Alan
	L: Tim		1.5	1
Week 11		26-Apr
		L: Tim	1.5	0
Week 12	29-Apr	3-May
	T: Tim
	L: Tim	L: Alan	2.5	1.5
Week 13	6-May
	T: Tim
	L: Tim		2.5	0
			36.5	11.5

Syllabus

[click here]