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: 12. 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:
minimize Φ =
∑
i
|xi|p, subject to Ax = b,
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: 19. 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
G(x) =
δn√
2πσ
exp
(
− (x− µ)
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
Ai,j = G(xi − xj) = δn√
2πσ
exp
(
− (xi − xj)
2
2σ2
)
(1)
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 = UWV T is satisfied.
f.) Compute the pseudoinverse A† of A by using the formula A† = VW †UT 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 WW † =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: 26. 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
χ
(a,b]
(x) =
{
1 for a < x ≤ b
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 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.