COMP0114 Inverse Problems in Imaging.

Coursework 1

Introduction
This coursework covers material in the first three weeks of the module. It is divided into three
parts which roughly will correspond to the material in each week; however you can carry out
the assignment in the time that suits you, with all parts being handed in as a single submission.
The assignments will be closely related to the support in the lab classes which you should attend
to get help with completing them.

Tasks
——————————————————————————————————————
Week 1: 14. January
——————————————————————————————————————
1. Solving Underdetermined Problems (30%)

As explained in lectures the linear equation x1 + 2x2 = 5 is used to introduce the concept of
minimum norm solutions of underdetermined problems:
X
minimize Φ = |xi |p , subject to Ax = b,
i
where in our case, A = (1 2), b = 5.

a.) Write a function of two variables, x and p, where x is a vector of length 2 and p is a scalar;
this function will compute the value of Φ as given above.
b.) Use library functions to compute solutions of the above optimization problem, for p =
1, 1.5, 2, 2.5, 3, 3.5, 4.
c.) Plot the solutions you have obtained as points on a 2D graph together with the line
representing the constraint equation x1 + 2x2 = 5. The result should look like Figure 1.

d.) Another solution method is to use the Moore-Penrose generalised inverse

A† := AT (AAT )−1 ,

and then apply it to get xMP = A† b. Implement this solution and plot it on the same graph
as in the previous question. What value of p does this correspond to and why?
 Figure 1: Example for a line plot for Exercise 1

In parts 2 and 3 of the assignment we will implement discrete convolution of a 1D function by

an explict matrix vector multiplcation, analyse its behaviour and compare to other methods for
performing convolution.

——————————————————————————————————————
Week 2: 21. January
——————————————————————————————————————

2. Singular Value Decomposition (30%)

In this part we analyse the matrix representation of convolution using Singular Value Decompo-
sition (SVD).

a.) Set up a spatial grid on the interval [−1, 1] in n equally spaced steps of size δn. The grid
represents the values [x1 , . . . xn ] with xi = −1+(i−1)δn for i = 1, . . . , n and δn = 2/(n−1).
Make sure that x1 = −1 and xn = 1.
b.) Create a vector of values of the Gaussian function centred at µ = 0 with σ = 0.2, given by

(x − µ)2
 
δn
G(x) = √ exp − .
2πσ 2σ 2
You should evaluate this function at the grid points you create in part a).
c.) Create the convolution matrix of size n × n with entries

(xi − xj )2
 
δn
Ai,j = G(xi − xj ) = √ exp − (1)
2πσ 2σ 2
d.) Plot the matrix A as an image, where A is considered as a 2D-array for the case n = 100.
e.) Compute the SVD of matrix A using library functions. You should obtain three matrices
U , W , V , where W is a diagonal matrix of same size as A containing the singular values.
Verify that the equation A = U W V T is satisfied.
 f.) Compute the pseudoinverse A† of A by using the formula A† = V W † U T as given in lectures.
This requires you to create a method for constructing W † . For the case n = 10, check that
this has the property W W † = W † W = Idn where Idn is the n × n Identity matrix. Check
also that AA† = A† A = Idn .
g.) Repeat the last two steps for n = 20. What do you observe? Choose n = 100 again
and plot the first 9 columns of V , the last 9 columns of V , and the singular values on a
logarithmic scale, i.e. log(diag(W )).

——————————————————————————————————————
Week 3: 28. January
——————————————————————————————————————

3. Convolutions and Fourier transform (40%)

In the following we want to examine the convolution of a 1D signal; we define a step function
on the interval [−1, 1] by

f (x) = χ(−0.95,−0.6] (x) + 0.2χ(−0.6,−0.2] (x) − 0.5χ(−0.2,0.2] (x) + 0.7χ(0.4,0.6] (x) − 0.7χ(0.6,1] (x),

where the characteristic function of an interval (a, b] is defined as

(
1 for a < x ≤ b
χ(a,b] (x) =
0 otherwise.

Here’s a plot of f in Figure 2.

Figure 2: The step function f

a.) Create a function for f as above and plot it on a grid on the interval [−1, 1]. Choose a
sufficiently large number of grid points n to resolve the jumps.
b.) Compute the matrix A as in part 2 for σ = 0.05, 0.1, 0.2 and plot the singular values.
c.) Verify that the plot of the singular values follows (half) a Gaussian function and determine
the variance of this Gaussian in each case.
d.) Perform the convolution of the function f with the matrix A (by matrix multiplication)
for all three choices of σ and plot the result.
 e.) Since convolution is equivalent to multiplication in Fourier space, perform convolution by
multiplication in Fourier space for the three choices of σ and plot the result (remember to
take the inverse Fourier transform); comment on any differences that you observe.
f.) Repeat the convolution with the matrix A using periodic boundary conditions when as-
sembling A.

Report
Write one report for all 3 parts. Explain your method and present your results and figures. Make
sure that you provide an answer to all questions. The total length of the report would normally
be between 6-10 pages. Submit your report using Moodle. Code can be uploaded separately.