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^* $$

is the thin SVD of the regularized matrix. Solving the regularized least squares problem the solution is given by

$$ \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)$.

  • $\begingroup$ Thanks for the nice answer! $\endgroup$
    – Slugger
    Nov 9 '15 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.