Stability of Tikhonov Regularization

Question

I'm learning about Tikhonov regularization

$$\underset{x\in X}{\arg\inf}\left\{||Ax-b||^2+\lambda ||x||^2\right\}$$

I have read that the solution keeps the residual $||Ax-b||^2$ small and is stabilized through the $\lambda ||x||^2$ term. Can anyone help me understand why that is? I can see that the term prevents overfitting, but I can't quite see how it helps stabilizing.

Thanks in advance.

Answer 1

Assuming $\|\cdot\|$ is the $L_2$ norm, the solution for $x$ is \begin{align*} x = (A^T A + \lambda I)^{-1}A^T b \end{align*} The instability in this solution lies in the inverse. If $A$ have columns which are nearly linearly dependent, then $A^TA$ is "nearly non-invertible". In other words, the condition number will be very large. The $\lambda I$ helps stabilize this inverse, and will always lower the condition number.

Answer 2

In order to understand Thikonov's stabilization, it helps to first look at the ordinary least square solution $x^*$:

\begin{align*} x^* = (A^T A)^{-1}A^T b \end{align*}

We see that it's necessary to calculate the inverse of $A^T A$ and this might not be possible, if $A$ has nearly linearly dependent columns. But let's take a closer look onto this, by factorizing just the suspicious term by a singular value decomposition.

Then $A^T A = U \Sigma V^T$ where $U$ and $V$ are the eigenvectors and $\Sigma$ is a diagonal matrix that contains the non-zero eigenvalues. It's not of special interest here that $U=V$, but it is very important that the pseudoinverse $(A^T A)^{-1}$ is found by inverting $\Sigma$.

More specific, the reciprocal of each eigenvalue, let's say $\sigma_i$ has to be found. And this might get difficult, if two columns are nearly linear dependent. In this case, $\sigma_i$ is very small and the result of the division gets very large and tiny pertubations of $\sigma_i$ lead to large fluctuations of the inverse. It is possible to monitor such cases and as this answer already mentions the condition number is one of these indicators.

The solution that Thikonov provides to overcome the problem is simple, but very effective: just take a positive variable $\lambda$ and add it to the denominator. This will bound the overall result and stabilize the solution:

\begin{equation} \Sigma_{ii}^+ = 1 / (\sigma_i + \lambda) \end{equation}

As we now have identified the cause of instabilities and inserted a term that prevents them, we can add the same to our known equation and role it back: \begin{equation} U (\Sigma + \lambda I) V^T = U \Sigma V^T + \lambda U V^T = A^TA + \lambda I \end{equation}

And finally, we arrive at the well known:

\begin{align*} x^* = (A^T A + \lambda I)^{-1}A^T b \end{align*}