# Effect of the Tikhonov regularization on the Least Squares solution.

Consider the system $Ax = b$, where $b \notin \mathcal{R}(A)$. Then we look to find a least squares solution to this problem via $$x_{LS} =A^{\dagger}b$$ where $A^{\dagger} = V \Sigma^{\dagger}U^*$ is the Moore-Penrose pseudoinverse with $A = U\Sigma V^*$ is the SVD of $A$. Now due to numerical considerations we may want to swap to the system $$\begin{pmatrix} A \\ \tau I \end{pmatrix} x =\begin{pmatrix} b\\ 0 \end{pmatrix}.$$ This is called Tikhonov regularization. Now, the wikipedia article on this says that the least squares solution to this new system is given by $$\tilde{x}_{LS} = VDU^*b$$ where $D$ is the diagonal matrix with elements $\frac{\sigma_i}{\sigma_i^2 + |\tau| ^2}$. I tried to recreate this result in the following way:

In the original SVD of $A$ we have that the singular values are the positive roots of the eigenvalues of $A^*A$, i.e., $A^*Av_i = \sigma_i^2 v_i$. Now $$\begin{pmatrix} A^* & \bar{\tau} I \end{pmatrix} \begin{pmatrix} A \\ \tau I\end{pmatrix} v_i = (A^*A + |\tau |^2) v_i = (\sigma_i^2 + |\tau|^2) v_i.$$ Shouldn't the singular values of $\begin{pmatrix} A \\ \tau I \end{pmatrix}$ be $\sqrt{\sigma^2 + |\tau|^2}$?

Suppose that $A = U\Sigma V^*$ is the thin SVD of $A$. Then you are correct that the singular values of the regularized matrix are the diagonal elements of the matrix $S = \sqrt{\Sigma^2 + |\tau|^2 I}$. It follows that
$$\left[ \begin{array}{c} A\\ \tau I \end{array} \right] = \left[ \begin{array}{c} U\Sigma S^{-1}\\ \tau V S^{-1}\\ \end{array} \right] SV^*$$
$$\bar{x}_{LS} = VS^{-1} \left[ \begin{array}{cc} S^{-1}\Sigma U^* & \bar{\tau}S^{-1}V^*\\ \end{array}\right] \left[ \begin{array}{c} b\\ 0\\ \end{array} \right] = VS^{-2}\Sigma U^*b = VDU^*b,$$
where $D = S^{-2}\Sigma$. By the definition of $S$, $D$ is a diagonal matrix with elements $d_{ii} = \sigma_i/(\sigma_i^2 + |\tau|^2)$.