Tikhonov regularization using Newton's method or gradient descent

Question

In Tikhonov regularization an explicit solution denoted by $\hat {x}$, is given by

$$ \hat{x} = (A^TA + \Gamma^T\Gamma)^{-1}A^Tb$$

How can we solve the same problem using Newton's method or gradient descent?

Answer 1

Welcome to Math StackExchange!

Yes, you can. In this case, the loss function is given by $${\displaystyle \mathcal{L}(\mathbf{x}) = \|A\mathbf {x} -\mathbf {b} \|_{2}^{2}+\|\Gamma \mathbf {x} \|_{2}^{2}}$$ so the gradient of it is $$\nabla_{\mathbf{x}}\mathcal{L}(\mathbf{x}) = \nabla_{\mathbf{x}}(\|A\mathbf {x} -\mathbf {b} \|_{2}^{2}) + \nabla_{\mathbf{x}}(\|\Gamma \mathbf {x} \|_{2}^{2}) = (2A^\top A \mathbf{x} - 2A^\top b) + (2\Gamma^\top \Gamma \mathbf{x}).$$ Also, the hessian is given by $$\text{Hess} \;\mathcal{L}(\mathbf{x}) = 2(A^\top A + \Gamma^\top \Gamma).$$

With this gradient and this hessian, you can apply Newton's method or gradient descent.

Answer 2

The other answer by user326159 does calculate the gradient correctly. If you apply gradient descent you will get some kind of damped Landweber iteration and this will converge to the unique minimizer of the Tikhonov function (if you choose the stepsize not too large).

However, if you apply Newtons method, you will get the exact minimizer of the Tikhnov functional (the one you gave in your questions) in just one step.