3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what happened from step 2 to 3? don't think I understand. Is that where you used the Pythagorean theorem? $\endgroup$ – Charlie Parker Mar 28 '15 at 4:52
  • 1
    $\begingroup$ @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. $\endgroup$ – Algebraic Pavel Mar 28 '15 at 12:18
  • $\begingroup$ last question and I think I got this, last line, from step 1 to 2. How did that happen? $\endgroup$ – Charlie Parker Mar 28 '15 at 16:25
  • 1
    $\begingroup$ @CharlieParker Note that $U^Te=\pmatrix{u_1^T\\\vdots \\u_r^T}e=\pmatrix{u_1^Te\\\vdots \\u_r^Te}$. $\endgroup$ – Algebraic Pavel Mar 28 '15 at 16:29
  • $\begingroup$ But for orthogonal matrices, $U^T U = I$ not $U U^T $, you sure about your last tine? $\endgroup$ – Charlie Parker Mar 28 '15 at 18:40

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.