Sensitivity of the least squares method and matrix condition number

Question

It is my understanding that if we have a simple linear system such as

$$Ax = y$$

The condition number of $A$ provides an indication of how sensitive the solution $x$ will be in relation to changes in $y$. However, if I was to solve this linear system via SVD

$$x = V \Sigma^{-1}U^{T}y$$

Then there is no condition number as x is not been multiplied by anything?

I don't understand why that is the case, because if $y$ had an error then that would change the solution to $x$? Could someone please explain further? Many thanks.

Answer 1

Your line of reasoning amounts to saying "because $x = A^{-1}y$, there is no condition number" to the system of equations. That's false.

You can write the system in two ways. Either as $Ax = y$, or (if you want to use SVD) $(U\Sigma V^T) x = y$. In the case that $A$ is invertible, we may solve this system as $$ x = A^{-1}y = V\Sigma^{-1}U^Ty $$ Whichever way you write these equivalent equations, we can see that changing the value of $y$ affects the value of $x$. The extent of this effect is captured by the condition number.

As it turns out, the condition number of $A$ is the same as the condition number of $\Sigma$.

Answer 2

There is no magic. Your SVD solution corresponds to a Moore-Penrose pseudo inverse, so it suffers from the usual sensitivity to a high condition number.

Answer 3

The sensitivity of the least squares problem is derived in Golub and Van Loan's book Matrix Computations, 3e, section 5.3.7.

Start with the linear system $$ \mathbf{A}x = b. $$ The matrix condition number is $\kappa_{2}\left( \mathbf{A} \right)$, the error $$ \rho_{LS} = \lVert \mathbf{A}x_{LS} = b \rVert_{2}, $$ the machine noise is $\epsilon$, the ideal solution is $x$, the computed solution is $\hat{X}$, and the angle $$ \sin \theta = \frac{\rho_{LS}}{\lVert b \rVert_{2}}. $$ The sensitivity of the solution is $$ \frac{\Vert \hat{x} - x \rVert_{2}}{\lVert x \rVert_{2}} \le \left\{ \frac{2}{\cos \theta} \kappa_{2}\left( \mathbf{A} \right) + \tan \theta \,\kappa_{2}\left( \mathbf{A} \right)^{2} + \mathcal{O}\left( \epsilon^{2}\right) \right\}. $$

Additional noise will be introduced by the solution method. For example, forming the normal equations essentially squares the condition number. Modern efficient least squares solvers exploit Givens rotations and Householder reflections to reduce the effects of noise.