MA590 Homework 6 Solved

Description

1     Consider the Conjugate Gradient Least Squares (CGLS) algorithm for solving the least squares problem

x

via the normal equations

G^TGx = G^Ty.

• Code your own function in MATLAB implementing the CGLS algorithm. Clearly indicateyour function input(s), output(s), and stopping criteria.
• 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 N² × 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.

• Add noise e to the blurred image from part (b) with relative noise level ||e||₂/||y_true||₂ = 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?
• Plot the discrete L-curve for the CGLS solutions from part (c); you should note that theresidual 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 x_true. 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   Implement the method of gradient descent with exact line search for minimizing

. 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.