MA 590  Homework 6 

MA 590 
Homework 6 
Problems
1 (20 points) Consider the Conjugate Gradient Least Squares (CGLS) algorithm for solving
the least squares problem
min
x
||Gx − y||2
2
via the normal equations
G
TGx = G
Ty.
(a) Code your own function in MATLAB implementing the CGLS algorithm. Clearly indicate
your function input(s), output(s), and stopping criteria.
(b) Test your CGLS function from part (a) on the blur test problem from ‘Regularization Tools’,
which is a small image deblurring problem. Both the exact “sharp” image and the blurred
image are N × N, and they are represented as N2 × 1 vectors stacking their columns.
Note: You can use the command X = reshape(x,N,N) to go from the stacked representation
of the image to the image itself. To display the image, you can use the function imagesc
together with the commands axis image and colormap gray or the function imshow(X,[])
(the latter requires MATLAB’s Image Processing Toolbox).
Let N = 64 and generate the test problem with blur(N,10,1.4) (the second input parameter controls the sparsity of G, the third controls the amount of blurring). Plot the sharp and
blurred N ×N images. Without adding noise to the data, perform a number of CGLS iterations. Plot some of the iterates as images, and comment on the quality of the reconstruction
as the number of iterations increases.
(c) Add noise e to the blurred image from part (b) with relative noise level ||e||2/||ytrue||2 = 0.1,
and repeat the CGLS computations. Comment on the quality of the reconstruction as the
number of CGLS iterations increases in this case – how does the noise affect the results?
(d) Plot the discrete L-curve for the CGLS solutions from part (c); you should note that the
residual and solution norms vary slowly with the number of iterations. Try to locate the
corner of the L-curve, and compare that solution with the solution that is closest to xtrue.
Does the L-curve work for this problem and method? How does the performance of the
L-curve criterion depend on the relative noise level and the amount of blurring? Discuss
your findings.
2 (10 points) Implement the method of gradient descent with exact line search for minimizing
||Gx − y||2
2
. Your implementation should be careful to avoid computing G
TG. Apply this
method to either the phillips or shaw test problem (your choice!), as well as the blur test
problem described in Problem 1 above, and compare your solution to the solution obtained
using CGLS. Discuss your results, in terms of both solution quality and running time. Also
comment on how adding noise to the data affects your results.
BONUS: If you’re feeling random, try implementing stochastic gradient descent! Compare
your solution with those obtained using the two other methods considered in this problem,
and discuss your results.
Note: For any of the above problems for which you use MATLAB to help you solve, you must
submit your code/.m-files as part of your work. Your code must run in order to receive full credit.
If you include any plots, make sure that each has a title, axis labels, and readable font size, and
include the final version of your plots as well as the code used to generate them.
2