Math Blog #2. How to Solve an Inverse Problem: Regularization

In my last math blog, I introduce what an inverse problem is. We used the notation 

(1) z=Au,

and said that the goal is to estimated u given z and A, where A is assumed to be a linear operator.

We also said that in inverse problems, our interest is on solving problems of the form (1) that fail one of the three conditions for well-posedness: (i) existence of a solution u; (ii) uniqueness of that solution; and (iii) continuous dependence of the solution u on z and A.

If (i) or (ii) fails, we can solve instead

u_ls = {argmin_u ||Au-z||^2 s.t. ||u|| is minimized}.

This minimum norm least squares solution is given by

(2) u_ls =pinv(A'*A)*(A'*z)    

where pinv denotes psuedo-inverse.

If (iii) fails, the mapping (A,z)-->u_ls defined by (2) is discontinuous, and we have to use regularization to make the problem well-posed. Tikhonov was one of the first to address this issue. He suggested solving instead

(3) u_alpha = argmin_u {||Au-z||^2 + alpha*||u||^2},

which is known as Tikhonov regularization. Problem (3) is now well-posed with a unique solution  

u_alpha = (A'*A+alpha*I)\(A'*z),

where \ denotes multiplication by the inverse matrix.