# What is the upper bound on the error of the solution of a noise perturbed linear system $Mx=b$?

Let $x$ be solution to the following linear system:

$$Mx = b$$

and let $\tilde{x}$ be the solution to the above linear system with some additive noise:

$$M \tilde{x}= \tilde{b}$$

where $\tilde{b} = b + e$

let $\sigma_{min}(M)$ denote the smallest singular value of matrix $M$.

I was trying to verify rigorously why:

$$\| x - \tilde{x} \| \leq \frac{ \| b - \tilde{b} \|}{\sigma_{min}(M)}$$

was true. However, I was unsure how to do it correctly.

This is what I have tried:

Notice that (if we assume a bound on the condition number, hence invertibility of M), then M is invertible and we get:

$$\tilde{x}= M^{-1}\tilde{b} = M^{-1}(b+e) = x+M^{-1}e$$

Now $\| x - \tilde{x} \|$ is:

$$\| x - \tilde{x} \| = \| M^{-1}e \|$$

To relate the singular values of M to the equation above, lets bring in its SVD, $M^{-1} = (U \Sigma V^T)^{-1} = V \Sigma^{-1} U^T$:

$$\| x - \tilde{x} \| = \| M^{-1}e \| = \| V \Sigma^{-1} U^T e \| = \| \sum^{r}_{j=1} \frac{1}{\sigma_j} v_j u_j^T e\|$$

By triangle inequality:

$$\| \sum^{r}_{j=1} \frac{1}{\sigma_j} v_j u_j^T e\| \leq \sum^{r}_{j=1} \| \frac{1}{\sigma_j} v_j u_j^T e\|$$

After this point a got a little stuck, however, I had a few ideas that looked promising but wasn't sure how to use them. It feels that if the singular vectors are orthonormal, then taking the norm yields 1 which together with the triangle inequality again could yield an upper bound of the sum of the reciprocal of the singular values? Seems like a true statement, however, might this upper bound to lose and its just the wrong direction for the proof?

To continue from the stuck-point, since $v_j$'s are orthonormal, the Pythagorean theorem gives $$\left\|\sum_{j=1}^r\frac{1}{\sigma_j}v_ju_j^Te\right\|_2^2= \left\|\sum_{j=1}^r\frac{u_j^Te}{\sigma_j}v_j\right\|_2^2 =\sum_{j=1}^r\frac{|u_j^Te|^2}{\sigma_j}\leq\frac{1}{\sigma_{\min}(M)}\sum_{j=1}^r|u_j^Te|^2.$$ The last touch is due to $$\sum_{j=1}^r|u_j^Te|^2=\|U^Te\|_2^2\leq\|U\|_2^2\|e\|_2^2\leq\|e\|_2^2.$$
• @CharlieParker Yes, exactly there; there was also a "typo" which is fixed now. You can see, what you start with is a combination of orthogonal vectors $w_j:=(u_j^Te/\sigma_j)v_j$. Hence square of the norm of their sum is the sum of squares of their norms. The norm of $w_j$ is simply the magnitude of the scalar $u_j^Te/\sigma_j$ since $v_j$ is normalized. – Algebraic Pavel Mar 28 '15 at 12:18
• @CharlieParker Note that $U^Te=\pmatrix{u_1^T\\\vdots \\u_r^T}e=\pmatrix{u_1^Te\\\vdots \\u_r^Te}$. – Algebraic Pavel Mar 28 '15 at 16:29
• But for orthogonal matrices, $U^T U = I$ not $U U^T$, you sure about your last tine? – Charlie Parker Mar 28 '15 at 18:40